NỘI DUNG BÀI VIẾT
Giới thiệu
Thuật toán sắp xếp chọn (Selection Sort) là thuật toán chọn phần tử nhỏ nhất từ mảng chưa được sắp xếp trong mỗi lần lặp và đặt phần tử đó ở đầu mảng chưa được sắp xếp.
Ý tưởng thuật toán sắp xếp chọn
Bước 1
Chọn phần tử đầu tiên trong mảng là minimum.
Bước 2
So sánh minimum với phần tử thứ hai. Nếu phần tử thứ hai nhỏ hơn minimum, đánh dấu phần tử thứ hai là minimum.
So sánh minimum với phần tử thứ ba. Một lần nữa, nếu phần tử thứ ba nhỏ hơn minimum, đánh dấu phần tử thứ ba là minimum, nếu không thì bỏ qua. Quá trình tiếp tục cho đến phần tử cuối cùng.
Bước 3
Sau mỗi lần lặp, giá trị minimum được đặt ở phía trước mảng chưa được sắp xếp.
Bước 4
Đối với mỗi lần lặp, lập chỉ mục bắt đầu từ phần tử chưa được sắp xếp đầu tiên. Bước 1 đến bước 3 được lặp lại cho đến khi tất cả các phần tử được đặt vào đúng vị trí của chúng.
Thuật toán sắp xếp chọn
selectionSort(array, size)
repeat (size - 1) times
set the first unsorted element as the minimum
for each of the unsorted elements
if element < currentMinimum
set element as new minimum
swap minimum with first unsorted position
end selectionSortCode language: PHP (php)Cài đặt thuật toán sắp xếp chọn
function selectionSort(array) {
var size = array.length;
for (var step = 0; step < size - 1; step++) {
var min_idx = step;
for (var i = step + 1; i < size; i++) {
// To sort in descending order, change > to < in this line.
// Select the minimum element in each loop.
if (array[i] < array[min_idx]) {
min_idx = i;
}
}
// put min at the correct position
var temp = array[step];
array[step] = array[min_idx];
array[min_idx] = temp;
}
}
var arr = [3, 5, -2, 14, -9, 30];
selectionSort(arr);
console.log(arr);
Code language: PHP (php)Kết quả
[-9, -2, 3, 5, 14, 30]Code language: JSON / JSON with Comments (json)Đánh giá thuật toán sắp xếp chọn
| Vòng lặp | Số lượng phép so sánh |
|---|---|
| 1 | (n-1) |
| 2 | (n-2) |
| 3 | (n-3) |
| ……. | …… |
| Cuối cùng | 1 |
Số lượng phép so sánh: (n – 1) + (n – 2) + (n – 3) +…..+ 1 = n(n – 1) / 2 gần bằng n2.
Độ phức tạp: O(n2)
Ngoài ra, chúng ta có thể phân tích độ phức tạp bằng cách quan sát số vòng lặp. Có 2 vòng lặp nên độ phức tạp là n*n = n2.
Độ phức tạp thời gian:
- Trường hợp xấu nhất: O(n2)
Nếu chúng ta muốn sắp xếp theo thứ tự tăng dần và mảng đã cho theo thứ tự giảm dần thì trường hợp xấu nhất sẽ xảy ra. - Trường hợp tốt nhất: O(n2)
Nó xảy ra khi mảng đã được sắp xếp. - Trường hợp trung bình: O(n2)
Nó xảy ra khi các phần tử của mảng có thứ tự lộn xộn (không tăng dần cũng không giảm dần).
Độ phức tạp thời gian của sắp xếp chọn là như nhau trong mọi trường hợp. Ở mỗi bước, bạn phải tìm ra phần tử tối thiểu và đặt nó vào đúng vị trí. Phần tử tối thiểu không được biết cho đến khi không đạt đến phần cuối của mảng.
Độ phức tạp không gian:
Độ phức tạp không gian là O(1) vì một biến temp được sử dụng để hoán đổi.
Ứng dụng của thuật toán sắp xếp chọn
Thuật toán sắp xếp chọn được sử dụng trong các trường hợp:
- Mảng có ít phần tử
- Chi phí hoán đổi không thành vấn đề
- Kiểm tra tất cả các phần tử là bắt buộc
- Chi phí ghi vào bộ nhớ quan trọng như trong bộ nhớ flash (số lần ghi / hoán đổi là O(n) so với O(n2) của sắp xếp nổi bọt)
Các bạn có thể tham khảo các bài viết hay về thuật toán sắp xếp trong JavaScript tại đây.
Hãy tham gia nhóm Học lập trình để thảo luận thêm về các vấn đề cùng quan tâm.
