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

Đây là bài 6/18 bài của series môn học Cấu trúc dữ liệu và giải thuật

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ử a0, a1, a2,…,an-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ử a0 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 a1, a2,…,an-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).

Mảng cần sắp xếp

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.

Tìm phần tử min trong mảng

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

Đổi chổ phần tử min với phần tử đầu tiên trong mảng đang xét

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

Lần lặp với i=0
Lần lặp với i=0
Lần lặp với i=1
Lần lặp với i=1
Lần lặp với i=2
Lần lặp với i=2
Lần lặp với i=3
Lần lặp với i=3

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(n2).

5/5 - (1 bình chọn)
Bài trước và bài sau trong môn học<< Thuật toán sắp xếp đổi chổ trực tiếp (Interchange Sort)Thuật toán sắp xếp nổi bọt (Bubble Sort) >>
Chia sẻ trên mạng xã hội:

Để lại một bình luận

Lưu ý:

1) Vui lòng bình luận bằng tiếng Việt có dấu.

2) Khuyến khích sử dụng tên thật và địa chỉ email chính xác.

3) Mọi bình luận trái quy định sẽ bị xóa bỏ.