Cấu trúc dữ liệu và thuật toán: Giải thuật sắp xếp theo độ dài giảm dần (Shell sort)

[Quoc_Khanh_Tran (Quốc Khánh Trần)]

Giải thuật sắp xếp theo độ dài giảm dần (Shell sort)

1. Ý tưởng thuật toán

Là cải tiến của Insert Sort. Trong Shell Sort, người ta chia dãy ban đầu thành các dãy con có độ dài h (trong Insert Sort thì h = 1). Tiếp theo thực hiện sắp xếp các dãy con đó (bằng các phương pháp sắp xếp khác, ở đây mình chọn Insert Sort). Giảm dần h ở các bước tiếp theo cho tới khi h = 1 thì dừng.

Cụ thể:

• 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: a[1], a[h+1], a[2h+1] , …
  – Dãy con thứ hai: a[2], a[h+2], a[2h+2] …
  – …
  – Dãy con thứ h: a[h], a[2h], a[3h], …
• 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=1.

2. Các bước của thuật toán

• Bước 1: Khởi tạo giá trị h theo công thức Knuth như sau: h=h*3+1 (h là khoảng - interval với giá trị ban đầu là 1)
• Bước 2: Chia list thành các sublist nhỏ hơn tương ứng với h
• Bước 3: Sắp xếp các sublist này bởi sử dụng sắp xếp chèn (Insert Sort)
• Bước 4: Lặp lại cho tới khi list đã được sắp xếp

3. Cài đặt (C++)

void shellSort(int a[], int n){
    int i, j, x, h=1;
    while (h <= n/3)
        h=h*3+1;
    while (h > 0){
        for (i = h; i<n; i++){
            x=a[i];
            j=i-h;
            while ((x<a[j]) && (j>=0)){
                a[j+h]=a[j];
                j=j-h;
            }
            a[j+h]=x;
        }
        h=(h-1)/3;
    }
}

4. Cơ chế hoạt động (sơ đồ dò vết)

Cho dãy số: |35|33|42|10|14|19|27|44|. Sắp xếp dãy số tăng dần.

Khi h = 4:

• Bước 1:
  i = 4; x = 14; j = 0; a[0] = 35;
  x < a[0] (14 < 35)
  –> a[4] = 35;
  –> j = -4;
  a[0] = 14;
  Ta có: |14|33|42|10|35|19|27|44|

• Bước 2:
  i = 5; x = 19; j = 1; a[1] = 33;
  x < a[1] (19 < 33)
  –> a[5] = 33;
  –> j = -3;
  a[1] = 19;
  Ta có: |14|19|42|10|35|33|27|44|

• Bước 3:
  i = 6; x = 27; j = 2; a[2] = 42;
  x < a[2] (27 < 42)
  –> a[6] = 42;
  –> j = -2;
  a[2] = 27;
  Ta có: |14|19|27|10|35|33|42|44|

• Bước 4:
  i = 7; x = 4; j = 3; a[3] = 10;
  x > a[3] (44 > 10)
  a[7]=44; //giữ nguyên giá trị

Ta được dãy đã sắp xếp tương đối: |14|19|27|10|35|33|42|44|

Khi h = 1:
Lúc này, vòng lặp for trong đoạn code Shell Sort bên trên tương đương với code Insert Sort dưới đây (j tương đương với pos):

void insertSort(int a[], int n) {
    int pos, i, x;
    for(i = 1; i < n; i++) {
        pos = i - 1;
        x = a[i];
        while((pos >= 0) && (x < a[pos])) {
            a[pos + 1] = a[pos];
            pos--;
        }
        a[pos + 1] = x;
    }
}

Sau khi “thực hiện Insert Sort” xong, h = 0, chương trình kết thúc.
Kết quả ta thu được 1 dãy đã sắp xếp theo trật tự tăng: |10|14|19|27|33|35|42|44|

5. Độ phức tạp của thuật toán

Đến nay chưa có một đánh giá tổng quát cho Shell Sort.