bubble sort

// bubble sorting
void bubble_sort(int *a, int size)
{
   int i, surface;
   //surface for putting the largest value after sorting for i loop
   for (surface = size - 1; surface > 0; --surface)
      // sorting like bubble, compare then and
      // switch them if larger bubble is on the left
      // hand side(a[i]), and finally we will get
      // the largest value
      for (i = 0; i < surface; ++i)
         if (a[i] > a[i+1])
            swap(a + i, a + i + 1);
}

// swap two values
void swap(int *a, int *b)
{
   int tmp = *a;
   *a = *b;
   *b = tmp;
}

程式請直接放入這支程式的 int main()上方,接著在那支程式的"func"的位置下面放上

   bubble_sort(b, arry_size);
   printf("The result of bubble sort:\n");
   for (i = 0; i < arry_size; ++i)
      printf("%d ", b[i]);
   puts("");

Bubble sort的演算法的基本原理就像是水中的泡沫一般,比較大的泡沫會不斷的往上爬.我們從最下面的那一個泡沫開始, 如果他比上面的那一個大顆,那麼就讓它往上爬,如果遇到同樣大顆或是比它大顆的,那麼就請留在原地,接著我們就用同樣方式繼續檢視它上面那顆,直到表層. 在code裡面我把水的表層取名叫surface. 這個code其實非常的短, 我們先來從最重要的部份開始講起.

      for (i = 0; i < surface; ++i)
         if (a[i] > a[i+1])
            swap(a + i, a + i + 1);

這個部分是bubble sort的主要原理部分, swap就是直接交換這兩個放入指標的值. 這個迴圈就是從泡泡的最底層一個一個去檢視泡泡的大小a[i]以及a[i+1], 如果底下那顆a[i]比上面那顆a[i+1]大顆,那麼就交換它們的位置,可以把它想成大顆的泡泡往上擠,硬把上面那顆小顆的往下壓. 當然遇到比他塊頭一樣或更大的(a[i] <= a[i+1])就不擠了,當然檢視一樣沒有中斷,就繼續檢視上面這顆,讓他繼續往上擠,照著這樣的方式我們就會檢視到水面,也就是surface這邊了. 

因此照這樣的想法來看的話,我們在這次檢視過後,到最後在水面的必然就是這次檢視中最大顆的,要強調的就是"這次檢視". 因為我們會有好幾次檢視. 所以跑完第一次surface迴圈,我們找到最大顆的並且她因為不斷的往上擠的緣故所以跑到了表層,也就是這個array的最右邊. 接下來的迴圈

   for (surface = size - 1; surface > 0; --surface)

就是把水面往下壓, 因為這次檢視中最大顆的已經跑出水面了, 我們就沒必要再次的去比較它, 我們只需要比較水面底下剩下的那些小嘍囉, 因此就是把水面往下壓,直到剩下那顆泡泡(surface > 0) 至於為什麼不要(surface >= 0)的原因就是因為剩下的那顆理所當然的就是最小的,沒有必要再去比較了. 

因此這個程式到最後array最右邊的就會是最大顆的,接著它的左邊那個就會是第二次檢視中最大顆的,那麼問題來了, 這左邊那顆會比右邊那顆還大嗎? 答案是不會, 因為我們在第一次檢視中選取的就會是最大顆的,不要忘記,最先冒出水面的當然是最大顆的. 因此接著之後冒出來的都必然會相等或是更小,不會更大. 

至於swap這支程式就不多做敘述了, 不在資料結構這邊討論的範疇,這是C語言的pointer, 有興趣的人請自行google pointer以及function的關聯. 基本上這支swap程式就是交換傳入的兩個value而已.