Thuật toán sắp xếp: SHELL SORT

Ý tưởng

Shell Sort là phương pháp cải tiến của Insertion Sort.

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 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

            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 (so với toàn bộ các phần tử trong dãy ban đầu có thể chưa đúng). Giảm khoảng cách h để tạo các dãy con mới 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 đã được so sánh với nhau để xác định trật tự đúng cuối cùng.

 

Giải thuật

            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 Insertion Sort.

            Bước 3i = i + 1;

                           Nếu ik : Lặp lại bước 2

                           Nếu i > k: Dừng

Chủ đề liên quan
Thuật toán sắp xếp: SHELL SORT

Cùng chuyên mục

Xem nhiều hôm nay