Các phương pháp sắp xếp NlogN

Giải thuật Sắp xếp cây

Khi tìm phần tử nhỏ nhất ở bước i, phương pháp sắp xếp chọn trực tiếp không tận dụng được các thông tin đã có được do các phép so sánh ở bước i-1. Vì lý do trên người ta tìm cách xây dựng một thuật toán sắp xếp có thể khắc phục nhược điểm này.

Mấu chôt để giải quyết vấn đề vừa nêu là phải tìm ra được một cấu trúc dữ liệu cho phép tích lũy các thông tin về sự so sánh giá trị các phần tử trong qua trình sắp xếp. Giả sử dữ liệu cần sắp xếp là dãy số : 5 2 6 4 8 1được bố trí theo quan hệ so sánh và tạo thành sơ đồ dạng cây như sau :

Trong đó một phần tử ở mức i chính là phần tử  lớn trong cặp phần tử ở mức  i+1, do đó phần tử  ở mức 0 (nút gốc của cây) luôn là phần tử lớn nhất của dãy. Nếu loại bỏ phần tử gốc ra khỏi cây (nghĩa là đưa phần tử lớn nhất về đúng vị trí), thì việc cập nhật cây chỉ xảy ra trên những nhánh liên quan đến phần tử mới loại bỏ, còn các nhánh khác được bảo toàn, nghĩa là bước kế tiếp có thể sử dụng lại các kết quả so sánh ở bước hiện tại. Trong ví dụ trên ta có :

Loại bỏ 8 ra khỏi cây và thế vào các chỗ trống giá trị -? để tiện việc cập nhật lại cây :

Có thể nhận thấy toàn bộ nhánh trái của gốc 8 cũ được bảo toàn, do vậy bước kế tiếp để chọn được phần tử lớn nhất hiện hành là 6, chỉ cần làm thêm một phép so sánh 1 với 6.

Tiến hành nhiều lần việc loại bỏ phần tử gốc của cây cho đến khi tất cả các phần tử của cây đều là -?, khi đó xếp các phần tử theo thứ tự loại bỏ trên cây sẽ có dãy đã sắp xếp. Trên đây là ý tưởng của giải thuật sắp xếp cây.

Cấu trúc dữ liệu Heap

Tuy nhiên, để cài đặt thuật toán này một cách hiệu quả, cần phải tổ chức một cấu trúc lưu trữ dữ liệu có khả năng thể hiện được quan hệ của các phần tử trong cây với n ô nhớ thay vì 2n-1 như trong ví dụ . Khái niệm heap và phương pháp sắp xếp Heapsort do J.Williams đề xuất đã giải quyết được các khó khăn trên.

Ðịnh nghĩa Heap :

Giả sử xét trường hợp sắp xếp tăng dần, khi đó Heap được định nghĩa là một dãy các phần tử  al, a2 ,... , ar thoả các quan hệ sau với mọi i Ỵ [l, r]:

1/.	a i  >= a 2 i
2/.	ai  >= a2i+1     {(ai , a2i), (ai ,a2i+1) là các cặp phần tử liên đới }

Heap có các tính chất sau :

• Tính chất 1 : Nếu al , a2 ,... , arlà một heap thì khi cắt bỏ một số phần tử ở hai đầu của heap, dãy con còn lại vẫn là một heap.
• Tính chất 2 : Nếu a1 , a2 ,... , anlà một heap thì phần tử  a1 (đầu heap) luôn là phần tử lớn nhất trong heap.
• Tính chất 3 : Mọi dãy al , a2 ,... , ar với 2l > r  là một heap.

Giải thuật Heapsort :

Giải thuật Heapsort trải qua 2 giai đoạn :

• Giai đoạn 1 :Hiệu chỉnh dãy số ban đầu thành heap;
• Giai đoạn 2: Sắp xếp dãy số dựa trên heap:
  • Bước 1:      Ðưa phần tử  nhỏ nhất về vị trí đúng ở cuối dãy:       r = n; Hoánvị (a1 , ar );
  • Bước 2:      Loại bỏ phần tử nhỏ nhất ra khỏi heap: r = r-1;       Hiệu chỉnh phần còn lại của dãy từ  a₁ , a₂ ... a_r thành một heap.
  • Bước 3:      Nếu r>1 (heap còn phần tử ): Lặp lại Bước 2       Ngược lại : Dừng

Dựa trên tính chất 3, ta có thể thực hiện giai đoạn 1 bắng cách bắt đầu từ heap mặc nhiên a_n/2+1 , a_n/2+2 ... a_n, lần lượt thêm vào các phần tử a_n/2, a_n/2-1, ., a₁ ta sẽ nhân được heap theo mong muốn. Như vậy, giai đoạn 1 tương đương với n/2 lần thực hiện bước 2 của giai đoạn 2.

• Ví dụ

Cho dãy số a:

12   2        8          5          1          6          4          15

Giai đoạn 1: hiệu chỉnh dãy ban đầu thành heap

Giai đoạn 2: Sắp xếp dãy số dựa trên heap :

thực hiện tương tự cho r=5,4,3,2 ta được:

• Cài đặt

Ðể cài đặt giải thuật Heapsort cần xây dựng các thủ tục phụ trợ:

      Sắp xếp với độ dài bước giảm dần - Shell sort

•   Giải thuật Sắp xếp chèn với độ dài bước giảm dần

Giải thuật ShellSort là một phương pháp cải tiến của phương pháp chèn trực tiếp. Ý tưởng của phương pháp sắp xếp là phân chia dãy ban đầu thành những dãy con gồm các phần tử  ở cách nhau h vị trí:

Dãy ban đầu : a1, a2, ..., an được xem như sự xen kẽ của các dãy con sau :

Dãy con thứ nhất : a1 ah+1 a2h+1 ...

Dãy con thứ  hai  : a2 ah+2 a2h+2 ...

....

Dãy con thứ  h     : ah a2h a3h ...

Tiến hành sắp xếp các phần tử trong cùng dãy con sẽ làm cho các phần tử  được đưa về vị trí đúng tương đối (chỉ đúng trong dãy con, so với toàn bộ các phần tử trong dãy ban đầu có thể chưa đúng) một cách nhanh chóng, sau đó giảm khoảng cách h để tạo thành các dãy con mới (tạo điều kiện để so sánh một phần tử  với nhiều  phần tử  khác trước đó không ở cùng dãy con với nó)  và lại  tiếp tục sắp xếp... Thuật toán dừng khi h = 1, lúc này bảo đảm tất cả các phần tử trong dãy ban đầu sẽ được so sánh với nhau để xác định trậ? tự đúng cuối cùng.

Yếu tố quyết định tính hiệu quả của thuật toán là cách chọn khoảng cách h trong từng bước sắp xếp và số bước sắp xếp. Giả sử quyết định sắp xếp k bước, các khoảng cách chọn phải thỏa điều kiện :

                       h_i  > h_i+1  và h_k = 1

Tuy nhiên đến nay vẫn chưa có tiêu chuẩn rõ ràng trong việc lựa chọn dãy giá trị khoảng cách tốt nhất, một số dãy được Knuth đề nghị :

h_i  = (h_i-1  - 1)/3 và h_k = 1, k = log₃n-1

• Ví duﺦnbsp; 127, 40, 13, 4, 1

hay

h_i  = (h_i-1 - 1)/2 và h_k = 1, k = log₂n-1

• Ví dụ : 15, 7, 3, 1 

Các bước tiến hành như sau:

• Bước 1:      Chọn k khoảng cách h[1], h[2], ..., h[k]; i = 1;
• Bước 2:       Phân chia dãy ban đầu thành các dãy con cách nhau h[i] khoảng         cách. Sắp xếp từng dãy con bằng phương pháp chèn trực tiếp;
• Bước 3:        i = i+1;          Nếu  i > k : Dừng          Ngược lại : Lặp lại Bước 2.      

•   Ví dụ

Cho dãy số a:

12   2        8          5          1          6          4          15

Giả sử chọn các khoảng cách là 5, 3, 1

h = 5 : xem dãy ban đầu như  các dãy con

h = 3 : (sau khi đã sắp xếp các dãy con ở bước trước)

h = 1 : (sau khi đã sắp xếp các dãy con ở bước trước)

Dừng .

• Cài đặt

Giả sử đã chọn được dãy độ dài h[1], h[2], ..., h[k], thuật toán ShellSort có thể được cài đặt như sau :

void ShellSort(int a[], int N, int h[], int k){ 

   int      step,i,j;

   int   x,len;

   for (step = 0 ; step <k; step ++)      {    

len = h[step];

for (i = len; i <N; i++)

{  x = a[i]; 

j = i-len; // a[j] đứng kề trước a[i] trong cùng dãy con

while ((x<a[j])&&(j>=0)// sắp xếp dãy con chứa  x

{// bằng phương pháp chèn trực tiếp

a[j+len]  = a[j];

j = j - len;

}

a[j+len] = x;

}

}

}

•   Ðánh giá giải thuật

Hiện nay việc đánh giá giải thuật Shellsort dẫn đến những vấn đề toán học rất phức tạp, thậm chí một số chưa được chứng minh. Tuy nhiên hiệu quả của thuật toán còn phụ thuộc vào dãy các độ dài được chọn. Trong trường hợp chọn dãy độ dài theo công thức h_i  = (h_i-1- 1)/2 và h_k = 1, k = log₂-1 thì giải thuật có độ phức tạp ? n^1,2 << n²