[ C ] Quick sort

Quick sort主要是找出基準點(pivot)，
然後把比他小的放左邊，比他大的放右邊，
最後左右兩邊再各自做Quick sort。

先給一個數字陣列，
int table[] = {10, 7, 6, 8, 32, 30, 41, 1, 56, 50, 5, 39, 61};

然後開始做sort，要從第0個位置到最後一個位置，
quicksort(table, 0, (size-1));

進到function內後，先宣告一些變數，
先把pivot值設成第一個數字，
int pivot = table[left];

然後左邊的起始值是第二個數字
int left_index = left+1;

最右邊的值為最後一個數字
int right_index = right;

接下來我要讓他無限迴圈的跑，
直到他這個迴圈內，把所以以pivot值為標準，
比他大的在左邊，比他小的在右邊。
直到left_index和right_index交錯後!!
代表第一次分完大小了。

左邊先分比pivot小的數字，如果遇到比pivot大的，
就馬上跳掉，並且記錄位置。
while(left_index <= right)
{
if(table[left_index] > pivot)
break;
left_index++;
}

右邊是要先比pivot大的數字，如果遇到比pivot小的，
也是要跳掉，並記錄位置。
while(right_index > left)
{
if(table[right_index] < pivot)
break;
right_index--;
}

然後把這兩個數字調換，
把大的丟去右邊，小的丟來左邊。
swap(&table[left_index], &table[right_index]);

如果兩個index還沒交錯，代表還沒比完，
那就繼續找下一個，直到結束。
if(right_index <= left_index)
break;

[10] [7] [6] [8] [32] [30] [41] [1] [56] [50] [5] [39] [61]
i:[32] j:[5]   把32和5調換   (第一輪)

[10] [7] [6] [8] [5] [30] [41] [1] [56] [50] [32] [39] [61]
i:[30] j:[1]   把30和1調換    (第二輪)

[10] [7] [6] [8] [5] [1] [41] [30] [56] [50] [32] [39] [61]
那就分成了以1和41為分界線，左邊比10小，右邊比10大

然後左邊原本在1的位置，右邊在30的位置，
再度進入迴圈，左邊遇到41跳掉，
右邊遇到41，繼續，遇到1跳掉，
所以最後因為交錯了，結束迴圈。
再把pivot的值10和右邊遇到的1這個值調換，
確保pivot值是在中間。
#######pivot : [10]##########
i:[10] j:[1]
[ 1] [ 7] [ 6] [ 8] [ 5] [10] [41] [30] [56] [50] [32] [39] [61]

之後左邊去做quick sort，
quicksort(table, left, right_index-1);

右邊也去做一次quick sort，
quicksort(table, right_index+1, right);


==========Console============
[10] [ 7] [ 6] [ 8] [32] [30] [41] [ 1] [56] [50] [ 5] [39] [61]
i:[32] j:[5]
[10] [ 7] [ 6] [ 8] [ 5] [30] [41] [ 1] [56] [50] [32] [39] [61]
i:[30] j:[1]
[10] [ 7] [ 6] [ 8] [ 5] [ 1] [41] [30] [56] [50] [32] [39] [61]
#######pivot : [10]##########
i:[10] j:[1]
[ 1] [ 7] [ 6] [ 8] [ 5] [10] [41] [30] [56] [50] [32] [39] [61]
#######pivot : [1]##########
i:[1] j:[1]
[ 1] [ 7] [ 6] [ 8] [ 5] [10] [41] [30] [56] [50] [32] [39] [61]
i:[8] j:[5]
[ 1] [ 7] [ 6] [ 5] [ 8] [10] [41] [30] [56] [50] [32] [39] [61]
#######pivot : [7]##########
i:[7] j:[5]
[ 1] [ 5] [ 6] [ 7] [ 8] [10] [41] [30] [56] [50] [32] [39] [61]
#######pivot : [5]##########
i:[5] j:[5]
[ 1] [ 5] [ 6] [ 7] [ 8] [10] [41] [30] [56] [50] [32] [39] [61]
#######pivot : [6]##########
i:[6] j:[6]
[ 1] [ 5] [ 6] [ 7] [ 8] [10] [41] [30] [56] [50] [32] [39] [61]
#######pivot : [8]##########
i:[8] j:[8]
[ 1] [ 5] [ 6] [ 7] [ 8] [10] [41] [30] [56] [50] [32] [39] [61]
i:[56] j:[39]
[ 1] [ 5] [ 6] [ 7] [ 8] [10] [41] [30] [39] [50] [32] [56] [61]
i:[50] j:[32]
[ 1] [ 5] [ 6] [ 7] [ 8] [10] [41] [30] [39] [32] [50] [56] [61]
#######pivot : [41]##########
i:[41] j:[32]
[ 1] [ 5] [ 6] [ 7] [ 8] [10] [32] [30] [39] [41] [50] [56] [61]
#######pivot : [32]##########
i:[32] j:[30]
[ 1] [ 5] [ 6] [ 7] [ 8] [10] [30] [32] [39] [41] [50] [56] [61]
#######pivot : [30]##########
i:[30] j:[30]
[ 1] [ 5] [ 6] [ 7] [ 8] [10] [30] [32] [39] [41] [50] [56] [61]
#######pivot : [39]##########
i:[39] j:[39]
[ 1] [ 5] [ 6] [ 7] [ 8] [10] [30] [32] [39] [41] [50] [56] [61]
#######pivot : [50]##########
i:[50] j:[50]
[ 1] [ 5] [ 6] [ 7] [ 8] [10] [30] [32] [39] [41] [50] [56] [61]
#######pivot : [56]##########
i:[56] j:[56]
[ 1] [ 5] [ 6] [ 7] [ 8] [10] [30] [32] [39] [41] [50] [56] [61]
#######pivot : [61]##########
i:[61] j:[61]
[ 1] [ 5] [ 6] [ 7] [ 8] [10] [30] [32] [39] [41] [50] [56] [61]



SourceCode

Ref.