Selection Sort là gì?
Selection Sort là một thuật toán sắp xếp đơn giản. Thuật toán này hoạt động bằng cách lặp lại qua mảng và chọn phần tử nhỏ nhất (hoặc lớn nhất, tùy thuộc vào yêu cầu) từ phần chưa được sắp xếp và trao đổi nó với phần tử đầu tiên của phần chưa được sắp xếp. Quy trình này được lặp lại cho đến khi không cần thiết phải trao đổi nữa, tức là mảng đã được sắp xếp.
Cụ thể, quy trình của Selection Sort bao gồm các bước sau:
- Chọn phần tử nhỏ nhất (hoặc lớn nhất) từ phần chưa được sắp xếp.
- Trao đổi phần tử đã chọn với phần tử đầu tiên của phần chưa được sắp xếp.
- Lặp lại các bước 1 và 2 cho đến khi không cần thiết phải trao đổi nữa
Selection Sort có những ưu điểm và nhược điểm riêng:
Ưu điểm:
- Đơn giản: Selection Sort rất đơn giản và dễ hiểu
- Ổn định: Selection Sort là một thuật toán sắp xếp ổn định, nghĩa là nó duy trì thứ tự tương đối của các phần tử bằng nhau
- Không yêu cầu bộ nhớ bổ sung: Selection Sort là một thuật toán sắp xếp ở chỗ, nghĩa là nó không yêu cầu bộ nhớ bổ sung để lưu trữ dữ liệu đã được sắp xếp
Nhược điểm:
- Không hiệu quả: Selection Sort không phù hợp với các tập dữ liệu lớn vì độ phức tạp thời gian trung bình và tồi tệ là O(n^2), nơi n là số lượng phần tử trong mảng
Selection Sort hoạt động như thế nào?
Giả sử chúng ta có một mảng sau: 64, 25, 12, 22, 11
Bước 1: Chọn phần tử nhỏ nhất từ phần chưa được sắp xếp, trong trường hợp này là 11.
Bước 2: Trao đổi phần tử đã chọn với phần tử đầu tiên của phần chưa được sắp xếp: 11, 25, 12, 22, 64
Bước 3: Chọn phần tử nhỏ nhất từ phần chưa được sắp xếp, trong trường hợp này là 12.
Bước 4: Trao đổi phần tử đã chọn với phần tử đầu tiên của phần chưa được sắp xếp: 11, 12, 25, 22, 64
Lặp lại các bước 1 đến 4 cho đến khi không cần thiết phải trao đổi nữa: 11, 12, 22, 25, 64
Vậy, mảng ban đầu 64, 25, 12, 22, 11 đã được sắp xếp thành 11, 12, 22, 25, 64 Source 3.
Cách cài đặt Selection Sort
function selectionSort(arr) { let len = arr.length; for (let i = 0; i < len; i++) { let minIndex = i; for (let j = i+1; j < len; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } // Swap elements if (minIndex !== i) { let tmp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = tmp; } } return arr;
}
Ứng dụng của Selection Sort
Thuật toán Selection Sort có một số ứng dụng:
- Mục đích giáo dục: Selection Sort được sử dụng rộng rãi trong giáo dục khoa học máy tính như một công cụ giảng dạy để giúp sinh viên hiểu được khái niệm về thuật toán sắp xếp.
- Kiểm tra và gỡ lỗi cho các thuật toán sắp xếp khác: Selection Sort có thể được sử dụng để kiểm tra và gỡ lỗi cho các thuật toán sắp xếp khác bằng cách phục vụ như một điểm tham chiếu đơn giản và trực tiếp.
- Trong đồ họa máy tính: Selection Sort phổ biến vì khả năng của nó phát hiện một lỗi nhỏ (như việc trao đổi chỉ hai phần tử) trong các mảng gần như đã được sắp xếp và sửa chúng với chỉ độ phức tạp tuyến tính (2n)
- Trong thuật toán điền đa giác: Selection Sort được sử dụng trong thuật toán điền đa giác, nơi các đường ranh giới được sắp xếp theo tọa độ x của chúng ở một dòng quét cụ thể (một đường song song với trục x), và với việc tăng dần y, thứ tự của chúng chỉ thay đổi (chỉ hai phần tử được trao đổi) tại các giao điểm của hai đường.
Nguồn tham khảo: