CTDL: Thuật toán Sắp xếp Shell (Shell sort)

[integer]

Được phát minh bởi Donald Shell vào năm 1959, Shell sort là thuật toán hiệu quả nhất trong nhóm các thuật toán sắp xếp có độ phức tạp O(n2). Đương nhiên, Shell sort cũng phức tạp nhất trong các thuật giải thuộc lớp này.


Shell sort là sự cải tiến của Insertion sort dựa vào hai nhận xét sau đây:

• Insertion sort sẽ rất hiệu quả nếu dữ liệu đầu vào hầu như đã được sắp xếp (đã được xếp trong từng khoảng cục bộ).
• Insertion sort hoạt động kém hiệu quả vì nó di chuyển các giá trị phần tử mỗ i lần chỉ một vị trí.

Shell sort là môt thuật toán sắp xếp với số gia giãm dần, thường được biết đến như là "comb sort" dành cho những khối chương trình hỗn độn chưa được làm sạch. Thuật toán tạo ra nhiều luồng chạy duyệt qua danh sách dữ liệu, và mỗi lần sắp xếp một số trong những tập dữ liệu được định kích cở như nhau (tập phân đoạn được tách ra từ tập dữ liệu ban đầu) dùng Insertion sort. Sau mỗi lần duyệt qua hết bộ dữ liệu thông qua các phân đoạn (có kích thước giãm dần >= 1) , kích thước của tập được sắp xếp trở nên lớn hơn, cho tới khi nó chứa toàn bộ danh sách dữ liệu. (Chú ý rằng do kích thước của tập tăng lên, số lượng tập dữ liệu cần được sắp xếp sẽ giảm dần) Điều này làm cho Insertion sort đạt tới trường hợp tối ưu nhất, chạy mỗi vòng lặp với độ phức tạp tiến tới O(n).

Các phần tử chứa trong mỗi tập phân đoạn thì không liền kề nhau - cụ thể hơn, nếu có i tập phân đoạn thì mỗi tập chứa các phần tử thứ i liên tiếp kể từ điểm xuất phát của tập đó. Ví dụ, nếu có 3 tập phân đoạn thì tập đầu tiên sẽ chứa những phần tử tại các vị trí 1, 4, 7 và cứ như thế tiếp tục. Tập thứ hai sẽ chứa những phần tử tại các vị trí 2, 5, 8, và cứ thế tiếp tục về sau; trong khi tập thứ ba sẽ chứa các phần tử ở vị trí 3, 6, 9, và tương tự kế đó.

Kích thước của tập dữ liệu được sử dụng trong mỗi lần duyệt dữ liệu có ảnh hưỡng lớn tới hiệu quả của việc sắp xếp. Vài nhà nghiên cứu hàng đầu về khoa học máy tính, trong đó có cả Donald Knuth và Robert Sedgewick đã phát triển những phiên bản phức tạp hơn cho shell sort nhằm nâng cao hiệu quả tính toán bằng việc xử lý một cách cẩn thận những tập phân đoạn sao cho có kích thước tốt nhất để dùng cho danh sách dữ liệu được cho.

Binh Nguyen - Bioz - ieev.org

--------------------------------------------------
Xem các chủ đề cùng chuyên mục:

• Lập trình Shell !! 07/12/2009
• copy n ki tu chuoi s tu vi tri thu m sang chuoi p(m,n khoi tao = 0) 14/05/2009
• Tính Tần Suất Từ Xuất Hiện Trong Chuỗi 14/05/2009
• Quản lý nhân sự 19/07/2009
• Đảo ngược số 19/07/2009
• ".:'Bai Tập Tiếp Của C Ôn Tập':." 20/06/2009
• Lệnh SWITCH một chút vui. 25/05/2009
• Các bài sắp sếp 26/05/2009
• Nhập 1 dãy số nguyên, sau đó in ra các giá trị và chỉ số lớn hơn x 19/07/2009
• Bài Tập Hàm-Tổ hợp 21/05/2009