Giải thuật và lưu đồ của thuật toán heap sort
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. 2. 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/. ai >= a2i 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 ,... , ar là 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 ,... , an là 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ừ a1 , a2 ... ar 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 an/2+1 , an/2+2 ... an, lần lượt thêm vào các phần tử an/2, an/2-1, ., a1 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ợ: 1. Thủ tục hiệu chỉnh dãy al , al+1 ...ar thành heap : Giả sử có dãy al , al+1 ...ar, trong đó đoạn al+1 ...ar, đã là một heap. Ta cần xây dựng hàm hiệu chỉnh al , al+1 ...ar thành heap. Ðể làm điều này, ta lần lượt xét quan hệ của một phần tử ai nào đó với các phần tử liên đới của nó trong dãy là a2i và a2i+1, nếu vi phạm điều kiện quan hệ của heap, thì đổi chỗ ai với phần tử liên đới thích hợp của nó. Lưu ý việc đổi chỗ này có thể gây phản ứng dây chuyền: void Shift (int a[ ], int l, int r ) { int x,i,j; i = l; j =2*i; // (ai , aj ), (ai , aj+1) là các phần tử liên đới x = a[i]; while ((j<=r)&&(cont)) { if (j }
} 2. Hiệu chỉnh dãy a1 , a2 ...aN thành heap :
Cho một dãy bất kỳ a1 , a2, ..., ar , theo tính chất 3, ta có dãy an/2+1 , an/2+2 ... an đã là một heap. Ghép thêm phần tử an/2 vào bên trái heap hiện hành và hiệu chỉnh lại dãy an/2 , an/2+1, ..., ar thành heap, .: void CreateHeap(int a[], int N )
{ int l;
l = N/2; // a[l] là phần tử ghép thêm
while (l > 0) do
{
Shift(a,l,N);
l = l -1;
}
} Khi đó hàm Heapsort có dạng sau : void HeapSort (int a[], int N)
{ int r; CreateHeap(a,N)
r = N-1; // r là vị trí đúng cho phần tử nhỏ nhất
while(r > 0) do
{
Hoanvi(a[1],a[r]);
r = r -1;
Shift(a,1,r);
}
} Ðánh giá giải thuật Việc đánh giá giải thuật Heapsort rất phức tạp, nhưng đã chứng minh được trong trường hợp xấu nhất độ phức tạp ? O(nlog2n) 2. 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 : hi > hi+1 và hk = 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ị : hi = (hi-1 - 1)/3 và hk = 1, k = log3n-1 Ví duﺦnbsp; 127, 40, 13, 4, 1 hay hi = (hi-1 - 1)/2 và hk = 1, k = log2n-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 12 2 8 5 1 6 4 15 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 len = h[step]; for (i = len; i { x = a[i]; j = i-len; // a[j] đứng kề trước a[i] trong cùng dãy con while ((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 hi = (hi-1- 1)/2 và hk = 1, k = log2-1 thì giải thuật có độ phức tạp ? n1,2 << n2 HeapSort co 3 ham : 1.MAX-Heapify . 2.BUILD MAX HEAP . 3 HEAPSORT
Thứ 1:
1.MAX-Heapify: chon ra phan tử lớn nhất
2.BUILD MAX HEAP: Xây dựng 1 MAX HEAP từ những phần tử đã chọn
3.HEAPSORT: sắp xếp Nếu bạn muốn xem chi tiết hơn thì vào địa chỉ này: http://www.uit.edu.vn/data/gtrinh/TH103/Htm/Bai04.htm Sao kỳ vậy, hỏi một đường mà trả lời một nẻo, hỏi giải thuật theo cách viết của thầy Hòa lại đem bài ở đâu trên mạng đưa vào-> pó tay |
