Thuật toán sắp xếp chọn - Selection Sort

Thuật toán sắp xếp chọn – Selection Sort

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 .

Thuật toán sắp xếp chọn - Selection Sort
Chọn phần tử đầu tiên

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.

Thuật toán sắp xếp chọn - Selection Sort
So sánh minimum với những phần tử còn lại

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.

Thuật toán sắp xếp chọn - Selection Sort
Đổi chỗ phần tử đầu tiên với minimum

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 - Selection Sort
Vòng lặp đầu tiên
Thuật toán sắp xếp chọn - Selection Sort
Vòng lặp thứ 2
Thuật toán sắp xếp chọn - Selection Sort
Vòng lặp thứ 3
Thuật toán sắp xếp chọn - Selection Sort
Vòng lặp thứ 4

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 selectionSort
Code 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ặpSố lượng phép so sánh
1(n-1)
2(n-2)
3(n-3)
…….……
Cuối cùng1

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.

Leave a Reply

Your email address will not be published. Required fields are marked *