Thuật toán Shell Sort (Sắp xếp Shell)

Shell Sort dựa trên Insertion Sort. Insertion Sort đôi khi phải dời khối lớn để chèn phần tử. Shell Sort tránh được nhiều lần dời nhờ sắp xếp với khoảng cách (gap) cụ thể. Sau mỗi pass, gap giảm dần.

Độ phức tạp Shell Sort

• Time Complexity: O(n log n) tốt nhất, các trường hợp khác phụ thuộc chuỗi gap
• Space Complexity: O(1)

Input và Output

Input: Danh sách chưa sắp xếp: 23 56 97 21 35 689 854 12 47 66
Output: Mảng trước sắp xếp: 23 56 97 21 35 689 854 12 47 66
Mảng sau sắp xếp: 12 21 23 35 47 56 66 97 689 854

Thuật toán

shellSort(array, size)
Input: Mảng dữ liệu, tổng số phần tử
Output: Mảng đã sắp xếp

Begin
  for gap := size/2; gap > 0; gap := gap/2 do
    for j := gap to size-1 do
      for k := j-gap down to 0 step -gap do
        if array[k+gap] >= array[k] then break
        else swap array[k+gap] with array[k]
      done
    done
  done
End

Ví dụ (C++)

#include <iostream>
using namespace std;

void swapping(int &a, int &b) { int t=a; a=b; b=t; }
void display(int *a, int n) { for(int i=0;i 0; gap /= 2)
        for(int j = gap; j < n; j++)
            for(int k = j-gap; k >= 0; k -= gap)
                if(arr[k+gap] < arr[k]) swapping(arr[k+gap], arr[k]);
                else break;
}

int main() {
    int n; cout << "Nhập số phần tử: "; cin >> n;
    int arr[n];
    cout << "Nhập phần tử:" << endl;
    for(int i=0;i> arr[i];
    cout << "Trước: "; display(arr,n);
    shellSort(arr,n);
    cout << "Sau: "; display(arr,n);
}

Kết quả

Nhập số phần tử: 10
Nhập phần tử: 23 56 97 21 35 689 854 12 47 66
Trước: 23 56 97 21 35 689 854 12 47 66
Sau: 12 21 23 35 47 56 66 97 689 854

Chuỗi gap phổ biến: Shell (n/2, n/4, ..., 1), Knuth (1, 4, 13, 40, ... = 3^k-1/2), Sedgewick, Ciura. Chuỗi gap tốt giảm đáng kể số lần so sánh và swap.