quick sorting的研究和改進

int divide_and_swap_with_d(int *a, int left, int right, long int d)
{
   // regart the first element as the pivot
   int pivot = a[left];
   int l, r;
   l = left;
   r = right + d;
   do {
      // find out l which the element is bigger/equal than
      // pivot from left hand side
      //do l++; while (l < r &&a[l] < pivot);
      do l += d; while (l<=right && a[l] < pivot);
      // find out r which the element is less/equal than
      // pivot from left hand side
      do r -= d; while (r>=left && a[r] > pivot);
      if (l < r) swap (a+l, a+r);
   } while (l < r);
   // swap both
   a[left] = a[r];
   a[r] = pivot;
   return r;
}

void quick_sort_with_d(int *a, int left, int right, long int d)
{

   int pivot;
   if (right > left) {
      // return the pivot in [left:right]
      pivot = divide_and_swap_with_d(a, left, right, d);
      // recursive sorting between [left:pivot-1]
      quick_sort_with_d(a, left, pivot - d, d);
      // recursive sorting between [pivot+1:right]
      quick_sort_with_d(a, pivot + d, right, d);
   }
}

// shell sort with quick sort kernel
void shell_plus_quick_sort(int *a, int size, int q, int p)
{
   int start, end;
   long int d = 1;
   // find out d_{n+1} < size
   do {
      d = q*d + p;
   } while (d < size);
   d = (d - p)/q;
   d = (d - p)/q;

   // use quick sort until division distance > 1
   while (d > 1) {
      end = size - (size%d);
      for (start = 0; start < d; ++start)
         quick_sort_with_d(a, start, start + end - d, d);
      d = (d - p)/q;
   }
   // normal quick sorting
   quick_sort(a, 0, size - 1);

}

雖說這是一個嘗試的改進呢，但事實上是一次失敗的改進。

這次的改進其實是使用shell sorting，但做sorting的kernel不是insertion，而是使用quick sorting。測量了速度來說，慘不忍睹阿，跟一般的quick又或是shell來比的話，真的速度太慢了。有興趣的人可以自行測看看速度。因為結果太差了，所以把這次的嘗試的失敗的改良放上來討論為何會失敗。

事實上寫到一半的時候大概知道這個跑起來不會比較快而且會慢很多，原因在於它和當時改進insertion使用link list的原因是一樣的，同樣是cache miss的問題。

最主要就是慢在這個kernel：divide_and_swap_with_d，是它造成有這種cache miss的問題，原因在於每次在比較a[l]或a[r]的時候，由於並非是連續的記憶體分佈，造成很有可能抓資料的時候，資料並沒有在cache上面。而必須要通過主記憶體去拿。這樣子一來一往就慢了，簡而言之就是遠水救不了近火。

那麼為什麼使用insertion sorting的kernel反而比較快?明明不是quick sorting本身比insertion sorting快嘛?怎麼可能會使用慢的kernel會比較快呢?

原因在於我們在做insertion sorting的kernel的時候，使用了一個tricky的方法，它並非如所宣稱的順序那樣sorting...比如說d=3的case，他會作這樣的sorting順序：
０　３　１　４　２　５　３　６　４　７　５　８.....
但以演算法宣稱的方式而言，理論上應該是要按照這樣的順序：
０　３　６　９　１２.......    １　４　７　１０　１３.....    ２　５　８　１１　１２.....
而事實上這兩種方式的結果將會是一模一樣的，只是先算後算的差別而已。
但更改這種方式將會造成速度上的差異，原因就在於cache memory一次都抓一把東西進去，以第一個方式去sorting的話，cache首先也許會抓個16個data進去，也就是在cache裡面,0~15這個範圍內的排序都在裡面做，不需要一直往記憶體那邊拿，但是如果採用第二個方法，每排6個data就得要再次的去記憶體那邊抓資料，會比較沒有效率。當然cache的實作我不是非常了解，他會一次抓幾個data不是很確定，但是可想而知的光是效率部分就會有差。


為了證實我的推論，於是二話不說改寫了下傳統的shell sorting，把他寫成第二個方法並與第一個方法比看看速度，以下是測試結果：
timing for shell 0(d=3*d+1): 13.000000
timing for shell 1 (d=3*d+1): 16.000000

shell 0是原本的寫法，而shell 1是使用演算法宣稱的方式，的確是比較慢，但是速度上差異不明顯，在此使用了20000000大小的array，random的range也是20000000。

以下是改寫成為演算法宣稱的source code：

void shell_sort_1(int *a, int size, int q, int p)
{
   // 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;
   int start;
   long int d = 1;
   // find out d_{n+1} < size
   do {
      d = q*d + p;
   } while (d < size);
   d = (d - p)/q;
   d = (d - p)/q;

   // use insertion sort until division distance = 1
   do {
      for (start = 0; start < d; ++ start)
         for (sofar = start + d; sofar < size; sofar += d) {
            a_sofar = a[sofar];
            prev = sofar - d;
            while (prev >= 0 && a_sofar < a[prev]) {
               a[prev + d] = a[prev];
               prev -= d;
            }
            a[prev + d] = a_sofar;
         }
      d = (d - p)/q;
   } while (d >= 1);
}

有興趣者請自行編譯研究。