shell sorting

// shell sort
void shell_sort(int *a, int size)
{
   // the element that want to insert in
   unsigned sofar;
   // previous element index before sofar
   int prev;
   // saving the value of a[sofar]
   int a_sofar;
   unsigned d = 1;
   // find out d_{n+1} < size
   do {
      d = 3*d + 1;
   } while (d < size);
   d = (d - 1)/3;
   d = (d - 1)/3;

   // use insertion sort until division distance = 1
   do {
      for (sofar = d; sofar < size; ++sofar) {
         // save a[sofar]
         a_sofar = a[sofar];
         // previous index start from sofar - 1
         prev = sofar - d;
         // while previous element is larger then
         // the value that we want to insert, then
         // push it to the right hand side
         while (prev >= 0 && a[prev] > a_sofar) {
            a[prev + d] = a[prev];
            prev -= d;
         }
         // then a[prev] is small or equal than a_sofar
         // so we can insert a[sofar] to this position
         a[prev + d] = a_sofar;
      }/* sofar */
      d = (d - 1)/3;
   } while (d >= 1);

}

以上是Shell sorting的程式碼，基本上他算是insertion sorting的延伸。你可以想像一列身高沒有排好的隊伍，原先的insertion sorting就是從頭開始一個一個的去排，把後面那個依據身高來往前
插入放到正確的身高位置，並以同樣的邏輯如此的排到最後一位。

而insertion sorting的缺點就是如同bubble sorting一樣，資料量越大的話那麼會有兩個要素就會跟著變大1.比較次數，2.資料搬移次數。只是insertion 比傳統的bubble sorting好一點的地方就是insertion的期望比較次數和資料搬移次數會是當下已排序量的一半。因此bubble sorting比較搬移次數如果是大約O(N^2)那麼insertion會是這個期望值的一半(雖然如此但成長倍數仍然是N^2)。

那麼如果本身資料已經有些排序的話，基本上insertion比較次數會比較少。因此藉由這樣的想法而發展出所謂的shell sorting。

他的邏輯很簡單。首先我給它一個number d 假設他是10好了。具體的作法如下：
1.從這隊伍中從第一位開始數每10個人一數我就叫人出來。如果整體有1000個人我這次就抽了一百個人出來。
2.對這十個人做insertion排序
3.接下來把這100個已排過順序人放回隊伍之後，接下來從第二位開始數，也是每10個人一屬然後一樣做insertion排序
4.直到從第9位開始數已經排序完之後，我們就縮短d,比如8 或7 或其他更小的數。
5.d越來越小直到d=1的時候就等於是普通的insertion sorting了。

而有人做演算法實驗發現如果d_{i+1}= 3*d_i +1的這種方式來算組距，當一開始d_n如果滿足d_{n+2} <N的時候,大量資料的情況之下是最理想的，時間複雜度將會到O(N^1.25)

因此以下是程式碼的對應：

前面的sofar，a_sofar，prev和Insertion sorting的notation用的是一樣的，sofar意思是目前排序的位置，也就是待排序數。a_sofar就是a[sofar]，prev就是在sofar之前的index。

   unsigned d = 1;
   // find out d_{n+1} < size
   do {
      d = 3*d + 1;
   } while (d < size);
   d = (d - 1)/3;
   d = (d - 1)/3;

在這邊一開始當然設的組距d是1，因為畢竟最後就是要做insertion sorting，而按照最佳的測試。d=3*d+1，當d_n滿足d_{n+2}<N的時候就是最好狀況。因此這邊首先ｄ＝１是因為最後要做的是insertion,而中間那個do while回圈就是要先找到d_n<N的狀況。接著往回回溯兩次就會是這個d_{n+2}<N了。

      for (sofar = d; sofar < size; ++sofar) {
         // save a[sofar]
         a_sofar = a[sofar];
         // previous index start from sofar - 1
         prev = sofar - d;
         // while previous element is larger then
         // the value that we want to insert, then
         // push it to the right hand side
         while (prev >= 0 && a[prev] > a_sofar) {
            a[prev + d] = a[prev];
            prev -= d;
         }
         // then a[prev] is small or equal than a_sofar
         // so we can insert a[sofar] to this position
         a[prev + d] = a_sofar;
      }/* sofar */

這個很熟悉嗎？是的沒錯，這就是普通的insertion sorting。只是它是每間隔d開始做一次sorting。首先為了教學方便我們先假設d=10。於是我們先從隊伍中第十個人開始與前面每隔１０個人就抽出來的人開始做insertion排序。當然在這邊就只有第一個人跟他做insertion排序。這兩個人排好之後就換第11個!注意這邊的邏輯會有點不太一樣。理論上來說是從隊伍的第20個開始跟原先這兩個排序好的傢伙再次排序，接著是第30,40,50... 最後才是從隊伍的第十一個開始與第二個人開始作排序，接著是第二十一個與第十一個,第二個人排序。如此下來的。但這邊的方式是不太一樣的。但基本上演算方式其實是和我們一開始的設計是一樣的，只是這邊的順序就是有經過調整。但是最後的排序方式都會是和我們的策略是一模一樣的。

因此在某個組距d之下都已經排好的話那麼就開始調整d的大小。

   do {
      d = (d - 1)/3;
   } while (d >= 1);

慢慢的縮小組距d，直到最後d=1做普通的一般insertion sorting為止。這就是shell sorting。基本上就是insertion sorting，只是是有組距版本的。