Đánh giá độ phức tạp của thuật toán shell sort năm 2024
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% Show 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 515 11 12 16 25 51 54 717)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 << n 2. Tại sao chúng ta cần nghiên cứu, thiết kế phân tích các thuật toán sắp xếp? Dưới đây là một số lý do quan trọng:
Bài viết này sẽ phân tích và so sánh các thuật toán sắp xếp khác nhau dựa trên các tham số khác nhau như độ phức tạp về thời gian, độ phức tạp về không gian, độ ổn định, trực tuyến so với ngoại tuyến, cách tiếp cận giải quyết vấn đề, v.v. So sánh dựa trên độ hiệu quảCác thuật toán sắp xếp dựa trên so sánh (based sorting)Trong các thuật toán sắp xếp dựa trên so sánh, chúng ta so sánh các phần tử để xác định thứ tự của các phần tử trong mảng đầu ra cuối cùng đã sắp xếp. Tất cả các thuật toán sắp xếp dựa trên so sánh đều có cận dưới độ phức tạp là nlogn. Chúng ta đã thấy rằng bất kỳ thuật toán sắp xếp dựa trên so sánh nào cũng phải mất
Như chúng ta đã thấy, độ phức tạp về thời gian trong trường hợp xấu nhất của các thuật toán sắp xếp ở trên có thể được phân loại thành hai phần: Các thuật toán sắp xếp Ngoài các phép toán so sánh, chúng ta còn thực hiện các dạng phép toán khác trong các thuật toán sắp xếp này. Nhưng số lượng các phép toán này sẽ luôn ít hơn số lượng các phép toán so sánh. Đó là lý do tại sao thao tác so sánh là yếu tố quyết định độ phức tạp của thời gian.
Các thuật toán so sánh tuyến tínhCó những thuật toán sắp xếp chạy nhanh hơn độ phức tạp thời gian Ví dụ về các thuật toán sắp xếp chạy trong thời gian tuyến tính là counting sort, radix sort, bucket sort,... Counting sort và radix sort giả định rằng đầu vào bao gồm các số nguyên trong một phạm vi nhỏ. Đồng thời, bucket sort giả định rằng đầu vào được tạo ra bởi một quá trình phân phối ngẫu nhiên các phần tử một cách đồng nhất trong khoảng nhất định. Các điều kiện đặc biệt với thuật toán sắp xếp thời gian tuyến tính:
Dưới đây là so sánh độ phức tạp về thời gian và không gian của một số thuật toán sắp xếp phổ biến: Các thuật toán sắp xếp tại chỗ (in-place)Thuật toán sắp xếp được áp dụng tại chỗ nếu nó không sử dụng thêm không gian để thao tác đầu vào nhưng có thể yêu cầu một không gian bổ sung nhỏ mặc dù không đủ cho hoạt động của nó. Hoặc chúng ta có thể nói một thuật toán sắp xếp sắp xếp tại chỗ nếu chỉ có một số lượng không đổi các phần tử mảng đầu vào được lưu trữ bên ngoài mảng.
Các thuật toán sắp xếp ổn địnhThuật toán sắp xếp ổn định nếu nó không thay đổi thứ tự của các phần tử có cùng giá trị Các thuật toán sắp xếp ổn định: buble sort, insertion sort, merge sort. Các thuật toán sắp xếp không ổn định: selection sort, quicksort, heapsort, counting sort. Các thuật toán sắp xếp ổn định hoạt động theo quy tắc: nếu hai mục so sánh bằng nhau thì thứ tự tương đối của chúng sẽ được giữ nguyên, tức là nếu cái này đứng trước cái kia trong đầu vào thì nó sẽ đứng trước cái kia trong đầu ra. Tính ổn định là điều cần thiết để duy trì thứ tự sắp xếp trên cùng một tập dữ liệu. Tính ổn định cũng không phải là vấn đề nếu tất cả các khoá đều khác nhau. Các thuật toán sắp xếp không ổn định có thể được triển khai đặc biệt để ổn định. Một cách để làm điều này là mở rộng thao tác so sánh để so sánh giữa hai đối tượng dữ liệu có khoá bằng nhau được quyết định bằng cách sử dụng thứ tự của các mục nhập trong dữ liệu đầu vào ban đầu như một bộ ngắt (tie-breaker). Tuy nhiên, việc ghi nhớ thứ tự này có thể cần thêm thời gian và không gian. Thuật toán sắp xếp trực tuyến và ngoại tuyếnThuật toán chấp nhận một phần tử mới trong khi quá trình sắp xếp đang diễn ra được gọi là thuật toán sắp xếp trực tuyến. Một thuật toán trực tuyến có thể xử lý từng phần đầu vào của nó theo thứ tự nối tiếp. Nói cách khác, các thuật toán sắp xếp trực tuyến có thể sắp xếp dữ liệu mà không cần có toàn bộ dữ liệu đầu vào ngay từ đầu. Ví dụ: insertion sort xem xét một phần tử đầu vào mỗi lần lặp và tạo ra giải pháp được sắp xếp một phần mà không xem xét các phần tử trong tương lai. Vì vậy, duy trì một danh sách được sắp xếp trong sắp xếp chèn, chúng ta có thể đặt từng mục đầu vào vào đúng vị trí của nó khi chúng ta nhận được thông tin đầu vào. Vì vậy, insertion sort là một thuật toán sắp xếp trực tuyến. Ngược lại, thuật toán ngoại tuyến cần dữ liệu đầu vào đầy đủ trong bộ nhớ ngay từ đầu hoặc nó yêu cầu tất cả các mục phải ở trong bộ nhớ trước khi bắt đầu sắp xếp. Ví dụ: Thuật toán selection sort sắp xếp một mảng bằng cách liên tục tìm phần tử nhỏ nhất từ phần chưa được sắp xếp và đặt nó ở đầu. Nó luôn yêu cầu quyền truy cập vào toàn bộ đầu vào, vì vậy nó là một thuật toán ngoại tuyến. |