Sắp xếp chọn

Sắp xếp chọn
Thông tin chung
Phân loại: Thuật toán sắp xếp Cấu trúc dữ liệu: Ngẫu nhiên Phức tạp thời gian: Trung bình $O(n^{2})$ Phức tạp dữ liệu: Không tốn thêm vùng nhớ Tối ưu: Thỉnh thoảng

Tư tưởng:

Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu tiên của dãy hiện hành. Sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2. Lặp lại quá trình trên cho dãy hiện hành đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.

Các bước thực hiện

• Bước 1: i=1
• Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n]
• Bước 3: Hoán vị a[min] và a[i]
• Bước 4: Nếu i<=n-1 thì i=i+1; Lặp lại bước 2
• Ngược lại: Dừng. n-1 phần tử đã nằm đúng vị trí.

Ví dụ minh họa

Ban đầu ta có mảng a với các giá trị:

7

2

5

4

1

3

8

6

Ví dụ code

void selection_sort(int arr[],int n)
 {
 int temp_for_swap;
 int min;
 
 for (int i = 0; i < n - 1; ++i) 
{
 min = i;
 
 for (int j = i + 1; j < n; ++j)
 {
 if (arr[j] < arr[min])
 {
  min = j;
 }
 }
 
 // Hoán vị.
 if (min != i)
 {
 temp_for_swap = arr[min];
 arr[min] = arr[pos];
 arr[pos] = temp_for_swap;
 }
 }
}

Cài đặt Sắp xếp chọn bằng Đệ quy:

#include <stdio.h>
 
int choose_smallest(
 int arr[],
 int n,
 int pos,
 int cur_min
) {
 if (pos == n)
 return cur_min;
 
 if (arr[pos] < arr [cur_min])
 cur_min = pos;
 
 return choose_smallest(arr, n, pos + 1, cur_min);
}
 
void selection_sort(
 int arr [],
 int n,
 int pos
) {
 int temp_for_swap;
 int min;
 
 if (pos == n - 1)
 return;
 
 min = choose_smallest(arr, n, pos + 1, pos);
 
 // Hoán vị.
 if (min != pos) {
 temp_for_swap = arr[min];
 arr[min] = arr[pos];
 arr[pos] = temp_for_swap;
 }
 
 selection_sort(arr, n, pos + 1);
}
 
int main(
) {
 int i, n;
 int arr [] = {10, 3, 6, 5, 2, 6, 7, 2, 6, 8, 10};
 
 n = 11;
 
 selection_sort(arr, n, 0);
 
 for (i = 0; i < n; ++i) {
 printf("%d ", arr[i]);
 }
 
 return 0;
}

Đánh giá

• Thuật toán ít phải đổi chỗ các phần tử nhất trong số các thuật toán sắp xếp(n lần hoán vị) nhưng có độ phức tạp so sánh là O(n²) (n²/2 phép so sánh).
• Thuật toán tốn thời gian gần như bằng nhau đối với mảng đã được sắp xếp cũng như mảng chưa được sắp xếp.

Xem thêm

• Sắp xếp nổi bọt
• Sắp xếp nhanh
• Sắp xếp chèn
• Sắp xếp trộn
• Sắp xếp vun đống