Phương pháp chọn trực tiếp
Giải thuật
Ta thấy rằng, nếu mảng có thứ tự, phần tử ai luôn là min(ai, ai+1, ., an-1). Ý tưởng của thuật toán chọn trực tiếp mô phỏng một trong những cách sắp xếp tự nhiên nhất trong thực tế: chọn phần tử nhỏ nhất trong N phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu dãy hiện hành; sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn N-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2; lặp lại quá trình trên cho dãy hiện hành… đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có N phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện N-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy. Các bước tiến hành như sau :
Bước 1: i = 1;
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 : Hoán vị a[min] và a[i]
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. //N-1 phần tử đã nằm đúng vị trí.
Ví dụ
Cho dãy số a: 12 2 8 5 1 6 4 15
Cài đặt
Cài đặt thuật toán sắp xếp chọn trực tiếp thành hàm SelectionSort
Pascal:
C++:
void SelectionSort(int a[],int N )
{
int min; // chỉ số 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ử hiện nhỏ nhất
Hoanvi(a[min], a[i]);
}
}
Ðánh giá giải thuật
Ðối với giải thuật chọn trực tiếp, có thể thấy rằng ở lượt thứ i, bao giờ cũng cần (n-i) lần so sánh để xác định phần tử nhỏ nhất hiện hành. Số lượng phép so sánh này không phụ thuộc vào tình trạng của dãy số ban đầu, do vậy trong mọi trường hợp có thể kết luận :
Số lần so sánh =
Số lần hoán vị (một hoán vị bằng 3 phép gán) lại phụ thuộc vào tình trạng ban đầu của dãy số, ta chỉ có thể ước lược trong từng trường hợp như sau :
Trường hợp | Số lần so sánh | Số phép gán |
Tốt nhất |
n(n-1)/2
|
0
|
Xấu nhất |
n(n-1)/2
|
3n(n-1)/2
|
Leave a comment