Selection Sort

Giải thuật Selection Sort là 1 trong các thuật toán sắp xếp kinh điển, cơ bản và dễ hiện thực, là thuật toán được tiếp cận sớm nhất khi bắt đầu học các giải thuật sắp xếp cơ bản. Trong 1 số trường hợp đơn giản, thuật toán này rất hữu hiệu, chẳng hạn với các mảng dữ liệu nhỏ không đòi hỏi phải tối ưu về thời gian.

Selection Sort

Ý tưởng

Chọn phần tử nhỏ nhất đưa về vị trí đầu tiên của mảng hiện tại và không cần quan tâm đến nó nữa. Khi đó mảng chỉ còn lại n - 1 phần tử của mảng ban đầu, tiếp tục xét từ phần tử thứ 2 của mảng.

Lặp lại cho đến khi dãy hiện tại chỉ còn 1 phần tử.

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

• Bước 1: i = 0.Bước 2: Tìm phần tử a[iMin] trong dãy hiện hành từ a[i] đến a[n-1].Bước 3: Đổi chỗ a[i] và a[iMin].Bước 4: Nếu i < n - 1 thì lặp lại bước 2 với i++ - Ngược lại thì dừng.

Hiện thực

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

Ưu và nhược điểm

• Số lần so sánh trong trường hợp tốt nhất là n(n-1)/2
• Số lần so sánh trong trường hợp xấu nhất là 3n(n-1)/2

Ưu điểm

• Thuật toán đơn giản, dễ hiện thực.
• Có số lần hoán đổi các vị trí ít.

Nhược điểm

• Chỉ được áp dụng trong các trường hợp có số lượng phần tử cần so sánh ít.
• Không nhận biết được mảng đã được sắp xếp.