3.2.4 - Shell Sort

1. 演算法

比較第$i$筆資料與第$i+$span筆資料，若前者大於後者，則兩者交換。

每一回合(每一個span)要做到都沒有發生交換才可以結束。

span的型式: $[\frac{n}{2^k}]$

void Sort(char *arr){
    int n = strlen(arr);
    int span = n/2;
    int flag = 0;
    while(span >= 1){
        while(flag != n-span){ //判斷是否整個回合都沒有swap
            flag = n - span;
            for (int i = 0; i < n-span; i++){
                if (arr[i] > arr[i+span]){  //swap
                    int temp = arr[i];
                    arr[i] = arr[i+span];
                    arr[i+span] = temp;
                    flag--;
                }
            }
        }
        span/=2;
    }
}

演算法分析:

$​input=\{5,7,8,9,3,1,4,2\}$

$span=[\frac{n}{2^k}]=\frac{8}{2^1}=4 \quad \Rightarrow \{3,1,4,2,5,7,8,9\}$ ，下一回合沒有發生交換，此回合結束。

$span = \frac{8}{2^2}=2 \quad \Rightarrow \{3,1,4,2,5,7,8,9\}$，下一回合沒有發生交換，此回合結束。

$span = \frac{8}{2^3}=1 \quad \Rightarrow \{1,3,2,4,5,7,8,9\} \Rightarrow \{1,2,3,4,5,7,8,9\}$，下一回合沒有發生交換，此回合結束。

span=1，shell sort結束。

2.性質

• Time Complexity:

  • Avg Case: $O(n^2)$

  • Worst Case: $O(n^2)$

  • Best Case: 和span的形式有關。 $O(n^{\frac{3}{2}})$

• Space Complexity: $O(1)$

Shell sorting is a unstable sorting method.