Thuật toán sắp xếp chọn trực tiếp (Selection Sort)

1. Ý tưởng thuật toán sắp xếp chọn trực tiếp

Giả sử cần sắp xếp tăng dần một danh sách có n phần tử a₀, a₁, a₂,…,a_n-1.

Chọn phần tử nhỏ nhất trong n phần tử của danh sách ban đầu. Tìm và đổi vị trí phần tử nhỏ nhất với phần tử đầu tiên trong danh sách. Lúc này, phần tử a₀ sẽ có giá trị nhỏ nhất trong danh sách.

Sau đó, xem danh sách cần sắp xếp hiện tại chỉ gồm n-1 phần tử, bắt đầu từ phần tử thứ 2 trong danh sách ban đầu. Tức là danh sách hiện tại chỉ gồm a₁, a₂,…,a_n-1.

Lặp lại quá trình trên cho danh sách hiện tại đến khi danh sách hiện tại chỉ còn 1 phần tử.

2. Các bước thực hiện thuật toán

Bước 1: i = 0;

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-1].

Bước 3: Đổi chỗ a[min] và a[i].

Bước 4: Nếu i < n-1 thì gán i = i+1; rồi lặp lại bước 2, ngược lại -> Dừng.

Minh họa thuật toán sắp xếp chọn trực tiếp

Mảng a gồm các phần tử cần sắp xếp với phần tử đầu tiên a[i]=20 (i=0).

So sánh các phần tử trong mảng a để tìm phần tử nhỏ nhất a[min]=2 với min=4.

Đổi chổ a[min]=2 với a[i]=20 (i=0).

Lặp lại các bước trên cho đến khi tất cả các phần tử trong mảng được sắp xếp xong (i = n-1). Lưu ý, sau mỗi lần lặp, giá trị của i tăng lên 1 (i=i+1), a[i] sẽ là phần tử đầu tiên cần đổi chổ với a[min].

3. Cài đặt thuật toán sắp xếp chọn trực tiếp với C++

void Selection_Sort(int a[], int n){
	int min;//vị trí phần tử nhỏ nhất trong dãy hiện hành
	for(int i=0; i<n-1; i++){
		min = i;
		for(int j=i+1; j<n; j++){
			if (a[j] < a[min]){
				min = j;//ghi nhận vị trí phần tử nhỏ nhất
			}
		}
		swap(a[min], a[i]);
	}
}

void main()
{
	int a[5] = {8, 4, 1, 6, 5};
	Selection_Sort(a, 5);
	cout<<"Mang sau khi sap xep:"<<endl;
	for(int i=0;i<5;i++){
		cout<<a[i]<<" ";
	}
	system("pause");
}

Kết quả

Mang sau khi sap xep:
1 4 5 6 8

Đánh giá giải thuật

Số phép so sánh trong trường hợp tốt nhất hoặc xấu nhất đều là n(n-1)/2. Độ phức tạp thuật toán là O(n²).