bubble sort的研究和改進

在看這個文章之前，請回去看bubble sort中關於surface是什麼意思
========================================================================
關於bubble sort有個麻煩的地方就在於如果是一般任意的資料形式， 它swap的次數非常的多。
而且每次都會從第0個element開始去做sorting直到surface。
因此它唯一的好處只是為了找出最大的value,然後放到array的最右邊。

你可以宣稱說它在每次從0到surface的sorting的時候會有某部分的排序.比如有個array：
12 3 7 8 8 15 89
然後做一次sorting後：
3 7 8 8 12 15 89

然後宣稱12在那次sorting之後已經排好了，所以不用在swap了。
是的 這種情況有可能發生， 但在資料很多的狀況之下省掉的swap的量根本沒有很多。 因為每次都一樣會從第0個element開始做sorting，在直到surface之前都會swap好幾次。
第一次sorting的機率也許是一半 0.5 ，假設有1000個element，
所以第一次sorting的swap次數大約是500，而第二次也許因為第一次sorting已經swap後的影響很棒，所以又省掉了一些，假設是300，於是總共swap800次。接著第三次第四次...直到一千次之前絕對是超過幾千次swap。

這是我用1000個random number (mod 100) 的array去測量swap次數的結果：
swap次數 = 241946
如果這些random number是mod 1000:
swap次數 = 254648

看起來似乎跟data的range差異性不大.

因此這swap的次數太過驚人了，swap要傳入兩個arguements，做了兩次copy reference的運算，再加上三個assignment的運算，雖然乍看之下不少，但swap本身的次數是非常多的！等於是有24萬次的swap運算。 先不看copy reference的運算次數，光看那assignment的運算有三次的話，總共的次數會有72萬次基本assignment運算！

如果這array是10000個要做sorting呢？它swap的次數是？
答案是：
swap次數25115210
等於光看這樣的結果的話，資料每多一個order, swap的次數就多了兩個order，也就是swap的次數是資料量N的平方倍 O(N^2)
------------------------------------------------------------------------------------------------

個人在分析了這麼誇張的狀況之下，想了一下， 根本這個bubble sorting對於處理量不小的資料是有非常多餘沒有任何意義的運算。因為在找出最大的value之前，我們根本不用在那邊跟小嘍囉周旋！了解嗎？我們只是要直接找出最大的老大是誰，不需要一個一個小嘍囉在那瘋狂的swap。

因此以這樣的想法去想的話，我們在每次surface decrease之前其實只需要做一次swap就可以了，也就是找出最大的那個，然後跟surface那個position swap就好了。 因此這樣一來swap的次數就會等同於資料量的大小。

以下就是根據這想法自行編寫的程式碼：

void big_one_sort(int *a, int size)

{
   // mark the index of the largest value
   unsigned max_ind;
   // mark the largest value
   int max_val;

   unsigned i, surface;
   for (surface = size - 1; surface > 0; --surface) {
      // regard the last one as the max value
      max_ind = surface;
      max_val = a[max_ind];
      // find out the max value and index
      for (i = 0; i < surface; ++i)
         if (a[i] > max_val) {
            max_val = a[i];
            max_ind = i;
         }
      // swap the last one with max one
      swap(a + surface, a + max_ind);
   }/* surface */
}

基本上程式碼和bubble sort是差不多的，只是多了兩個量：
max_val 是為了記錄在某次sorting下的最大值，
max_ind就是這個最大值所對應的index(也就是在這array內的位置)
因此當內圈的i loop跑完之後，我們便會找到除了surface這個element之前的最大的value和其位置
接著我們就直接swap surface的value和max_val 也就是最大的那個值和surface交換

當然也許會問，為什麼i loop不要檢視到surface這個值？ 理由在於：我們在i loop之前便已經把
max指定為surface那個值，也就是假定最後的那個是最大的。 接著我們在i loop之後就直接swap最後的那個以及最大的值， 因此會有兩個情形發生：
1. 找到的max_val比surface那個值還大， 那麼swap是沒什麼問題。
2. 找到的max_val比surface那個值還小， 那麼surface無疑就是最大的， 它和它自己swap沒什麼不好，當然也許多餘，但數學上是一樣的 (而且就數學機率上來說這個swap發生的機率= 1/surface 微乎其微)

而且最重要的是如果我們的for loop有檢視到surface，等於是我們至少會多一次運算，就是裡面的那個 if (a[i] > max_val)
這是無可避免的，但是如果我們的for loop並沒有到surface的話，我們少了這次運算，而且那個swap不管是哪種方案也照樣會去執行。
沒有任何理由去把這for loop跑到surface去。


也許你覺得這樣考量非常的龜毛沒必要，但細微的地方有時候常常會是速度上的差距。題外話。


因此最後比較這兩個速度的話...我用time.h的time函數去跑80000這樣大小的random array 速度上
big_one_sort會是bubble_sort的 33/9 = 366.67% 倍， 當然隨著資料量越多，這個差距會更加的恐怖。