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

Posted on by adminChuyên mục:Kiến thức Internet

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

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

Lần lặp với i=0Lần lặp với i=0Lần lặp với i=1Lần lặp với i=1Lần lặp với i=2Lần lặp với i=2Lần lặp với i=3Lầ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
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ầu chọn )

admin