STT 1 Trần Thị Hồng Khuyên Họ và Tên Phần trăm đóng góp[%] 20% Chữ kí 2 Trần Phương Linh 20% 3 Đinh Thị Thùy Linh 20% 4 Mai Đức Trung 20% 5 Nguyễn Anh Tuấn 20%
Thông tin tài liệu tham khảo: [1] Slide bài giảng của thầy Nguyễn Thanh Thụy. [2] vietjack/cau-truc-du-lieu-va-giai-thuat/giai-thuat-shell-sort.jsp [3] cs.wcupa/rkline/ds/shell-comparison.html [4] sites.google/site/nguoisaigonblog/giai-thuat-sap-xep-tinh-te/giai- thuat-shell-sort-dan-tri
1]Thuật toán sắp xếp shell sort
2]Ý tưởng: [4]Là giải thuật cải tiến từ Insertion sort. Ý tưởng chính của thuật toán là phân chia dãy ban đầu thành những dãy con mà mỗi phần tử của dãy cách nhau 1 vị trí là h. Insertion sort áp dụng sau đó trên mỗi dãy con sẽ làm cho các phần tử được đưa về vị trí đúng tương đối [trong dãy con] 1 cách nhanh chóng. Sau đó tiếp tục 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 tự cuối cùng. - 3]Giải thích [1]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 : a 1 , a 2 , ..., an được xem như sự xen kẽ của các dãy con sau : Dãy con thứ nhất : a 1 ah+1 a2h+ ... Dãy con thứ hai : a 2 ah+2 a2h+ ... .... 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
Giảm khoảng cách h để tạo thành các dãy con mới Dừng khi h= 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 hi = [hi-1 - 1]/3 và hk = 1, k = log 3 n- Ví dụ :127, 40, 13, 4, 1 hi = [hi-1 - 1]/2 và hk = 1, k = log 2 n- Ví dụ : 15, 7, 3, 1 h có dạng 3i+1: 364, 121, 40, 13, 4, 1 Dãy fibonaci: 34, 21, 13, 8, 5, 3, 2, 1 h là dãy các số nguyên tố giảm dần đến 1: 13, 11, 7, 5, 3, 1.
4]Thuật toán [1] B1 Chọn k khoảng cách h[1], h[2], ..., h[k]; i = 1; B2 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 B3 i=i+ nếu i>k :dừng Ngược lại , lặp lại bước 2 5]Cài đặt thuật toán
Giả sử ta cần sắp xếp mảng M có 10 phần tử sau [N=8]: M: 11 16 12 71 51 54 5 25 Chọn các khoảng cách là h=[5,3,1] -h=5 xem dãy ban đầu như các dẫy con
11 16 12 71 51 54 5 25 -h=3 sau khi đã sắp xếp các dãy con ở bước trước
11 5 12 71 51 54 16 25 -h=1 sau khi đã sắp xếp các dãy con ở bước trước
11 5 12 16 25 54 71 51
11 5 12 16 25 54 71 51
5 11 12 16 25 54 71 51
5 11 12 16 25 51 54 71
7]So sánh thuật toán [3] Thuật toán Selectionsort 0[n TH tốt nhất 2 ] TH xấu nhất 0[n 2 ] Insertionsort 0[n] 0[n 2 ] ShellsortQuicksort 0[n* log[n]] 0[n0[n* log[n]] 0[n1,5 2 ]] Mergesort 0[n* log[n]] 0[n* log[n]] Heapsort 0[n] 0[n* log[n]]
8]Độ phức tạp của thuật toán [4]Yếu tố quyết định chính của thuật toán chính 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 k. Nhưng phải thỏa 2 điều kiện sau: hi > hi+ và hk = 1 Các phần tử h không được là bội số của nhau nhằm tránh hiện tượng mỗi bước sắp thứ tự phải tổ hợp 2 nhóm mà bước trước chúng không hề có ảnh hưởng lẫn nhau. Điều mong muốn là ảnh hưởng giữa các nhóm khác nhau càng nhiều càng tốt. Việc đánh giá giải thuật Shell sort hiện nay rất phức tạp, thậm chí 1 số chưa được chứng minh. Nhưng có 1 điều chắc chắn là hiệu quả của thuật toá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 = log 2 -1 thì giải thuật có độ phức tạp tương đương n1,2