quick sorting

int divide_and_swap(int *a, int left, int right)
{
   // regart the first element as the pivot
   int pivot = a[left];
   int l, r;
   l = left;
   r = right + 1;
   do {
      // find out l which the element is bigger/equal than
      // pivot from left hand side
      do l++; while (a[l] < pivot);
      // find out r which the element is less/equal than
      // pivot from right hand side
      do r--; while (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;
}

// quick sorting
void quick_sort(int *a, int left, int right)
{

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

主要有兩個function，其實是可以寫成同一個function省記憶體。因為這邊這個quick sorting是很浪費記憶體空間的sorting，如果把一個function拆成兩個會更浪費記憶體。但為了教學和理解方便將它拆成兩部分。如果對於概念已熟稔，就把它們寫成同一個function來實作。

這個sorting在寫的時候根據經驗是非常容易寫錯的，雖然概念上很簡單，但我實作我的一本參考書把整個code一模一樣打上去的時候是不能run的。於是最後參考了Horowitz的資料結構而寫成。經過測試是沒問題的。

quick sorting的理論其實很簡單，就是把第一個element當做是基準值，接著從左邊開始往右找到一個大於等於基準值的第一個數，然後從右邊找到小於等於基準值的第一個數，接著把它們swap。接著繼續找直到從左邊找的和從右邊找的位置相交為止。然後把基準值換到最後從右邊找不到比它大的數的那個位置作swap。因此左邊的數就會比基準值小(或等於)，右邊的數就會比基準值大。接著再用同樣的方式從左邊到基準值的這一段做quick sorting，然後從基準直到右邊也做同樣的quick sorting。

以排隊的例子來說，簡單來講就是把隊伍中第一個抽出來，然後讓比他矮的排他左邊，比他高的排他右邊。排的方式就是從左邊開始找出比他高的，然後和從右邊開始找出比他矮的交換位置。一直持續的找找到位置是相交的為止。　最後就把那個原本的第一位排到那個和它自己一樣大又或者是比他小一點點的那個位置。

但是呢這時候雖然這個人的左邊都是比他矮的，但是就是未排序，因此用同樣的邏輯去排他左邊的那一堆人。右邊的也是同樣的方式。

因此最後將會每個人的右邊將會比他高，左邊的就會比他矮。這就是sorting的樣貌。

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

首先是這個程式的邏輯。if所包著的，就是確保我們在排的時候裡面還是在相交之前。而pivot = divide_and_swap(a, left, right);這一行在做的就是我們從左區間left到右區間right中做排列，抽出left這個位置的value當做基準值pivot，然後讓左邊的值都比pivot小，讓右邊的值都比pivot大，最後再返回pivot的位置。

然後用同樣的邏輯去排pivot左邊那群人，以及右邊那群人就是這邊程式的邏輯。有點像是二分搜尋法的感覺，只是多了左右交換使得左邊比較小而右邊比較大。
因此在divide_and_swap內:

   do {
      // find out l which the element is bigger/equal than
      // pivot from left hand side
      do l++; while (a[l] < pivot);
      // find out r which the element is less/equal than
      // pivot from right hand side
      do r--; while (a[r] > pivot);
      if (l < r) swap (a+l, a+r);
   } while (l < r);

從左邊找出l(L,不是123的1)這個位置，使得它的值比pivot大(或等於)。
用同用的邏輯從右邊找到r，其值比pivot小(或等於)。
如果這兩個位置沒相交的話，就讓它們兩個交換，因此如果最後的pivot放到這個相交點的話：

   a[left] = a[r];
   a[r] = pivot;

那麼經過do while迴圈後pivot左邊的那群value將會小於等於pivot，右邊的將會大於等於pivot。