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

Như đã trình bày ở giải thuật Interchange Sort thì có rất nhiều các giải thuật về bài toán sắp xếp nhưng giải thuật nào mang lại tính hiệu quả cao cho công việc cũng như dễ hiểu cho bạn đọc thì hôm nay chúng ta sẽ cùng tìm hiểu thêm về một giải thuật nữa mang tên là chọn trực tiếp hay còn gọi là Selection Sort.

Ý tưởng

Ý tưởng chính của thuật toán là xuất phát từ cuối (hoặc đầu) dãy, đổi chổ các cặp phần tử kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành, sau đó sẽ không xét đến nó ở vị trí tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i. Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét thì dừng giải thuật.

Giải thuật

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]

Bước 3:

Dùng hàm swap để đổi chỗ a[i] và a[min]

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

Ví dụ: Cho dãy A gồm 4 phần tử 10, 5, 14, 9. Hãy dùng giải thuật sắp xếp Selection Sort để minh họa.

Đầu tiên i=0. a₀ = 10. Gán cho 10 là giá trị nhỏ nhất.

Chạy từ a₁ đến a₃ xét thấy a₁ là phần tử nhỏ nhất ( min) nên đổi chỗ giữa a₀ và a₁.

Dãy mới: 5, 10, 14, 9.

Do đã tìm được phần tử nhỏ nhất của mảng đưa ra đầu mảng nên sẽ tăng i lên 1 đơn vị:

i=i+1=1. a₁= 10.

Chạy từ a₁ đến a₃ xét thấy a₃=9 là phần tử nhỏ nhất nên tiến hành đổi chỗ giữa a₁ và a₃.

Dãy mới: 5, 9, 14 , 10.

Tương tự từ a₁ đến a₃ không còn phần từ nào nhỏ hơn 9 nên i sẽ tăng lên 1 đơn vị:

i=i+1=2. a₂=14.

Chạy từ a₂ đến a₃ xét thấy a₃=10 là phần tử nhỏ nhất nên tiến hành đổi chỗ giữa a₂ và a_3.

Dãy mới: 5, 9, 10, 14.

Sau đó tăng i lên 1 đơn vị:

i=i+1=3. Do không thỏa i<n-1 nên chúng ta dừng giải thuật ở đây và nhận được dãy đã sắp xếp là:

5, 9, 10, 14.

Code C/C++

Hàm sắp xếp theo thuật toán Selection Sort:

void Sapxep(int a[], int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int min = i;
		for (int j = i + 1; j < n; j++)
			if (a[min]>a[j])
				min = j;
			swap(a[i], a[min]);
	}
}

Hàm đổi chỗ 2 phần tử ( Swap ): 

void swap(int &a, int &b)
{
	int x = a;
	a = b;
	b = x;
}

Hàm main:

void main()
{
	int A[100];
	NhapMang(A, N);
	Sapxep(A, N);
	printf("Mang sau khi sap xep la: ");
	XuatMang(A, N);
	getch();
}

Trước khi chạy hàm main các bạn phải có hàm nhập và xuất mảng 1 chiều. Các bạn có thể xem tại đây.

Kết quả:

SO PHAN TU:

6

Phan tu thu 0: 7

Phan tu thu 1: 11

Phan tu thu 2: 1

Phan tu thu 3: 4

Phan tu thu 4: 6

Phan tu thu 5: 0

Noi dung cua mang la:     7   11    1    4    6    0

Mang sau khi sap xep la:      0   1    4    6    7    11

Trên đây là một trong những thuật toán sắp xếp của bài toán C/C++. Selection Sort là một thuật toán giải quyết bài toán sắp xếp, còn rất nhiều các giải thuật sắp xếp khác mà chúng tôi sẽ gửi đến các bạn ở các ở các bài viết sau. Xem thêm Thuật toán sắp xếp nổi bọt (BubbleSort)

Chúc các bạn thành công.