[C] 各種Sorting

各個Sorting algorithm的複雜度:

Insertion Sort:
從 i=1 做到 i=n-1，每一round拿現在這個數與前面的數相比，若數字比前面的小，則將前面的數往後移，直到找到比它小的數，在插入比它小的數字的下一個位置。由於此方法從左邊開始，然後每一次數字的左邊一定是個被sort好的subarray，所以此方法不怕插入到不對的位置。

void insertion_sort(int* arr, int size){
    if(!arr)
        return;
        
    for(int i=0; i<size; i++){
        int target = arr[i];
        int j = i-1;
        while(target < arr[j] && j>=0){
            //move element to vacate the place
            arr[j+1] = arr[j];
            j--;
        }
        //find the proper place and place it
        arr[j+1] = target;
    }
}

Selection Sort:
從 i=0 做到 i=n-1，每一round從當個位置右邊的subarray中找出最小的數字，找到後與他交換位置。

void selection_sort(int* arr, int size){
    for(int i=0; i<size-1; i++){
        int min_pos = i;
        for(int j=i+1; j<size; j++){
            if(arr[j] < arr[min_pos])
                min_pos = j;
        }
        //swap
        int tmp = arr[min_pos];
        arr[min_pos] = arr[i];
        arr[i] = tmp;
    }
}

Bubble Sort:
做size-1次，每一次選擇0~size-1的範圍，結束後將範圍縮小一。每一次都兩兩交換數，直到把最大換到範圍的最末端。

void bubble_sort(int* arr, int size){
    size--;
    while(size){
        for(int i=0, j=i+1; i<size, j<=size; i++, j++){
            //swap
            if(arr[i] > arr[j]){
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        size--;
    }
}

Quick Sort:
Quick sort每回合利用一個數作為pivot，將front and end之間做partition。通常以最後一個數作為pivot，回合開始時，設定兩個位置，left_end(圖中是i) and right_end(圖中)，為的就是指出left part and right part的尾端，然後開始由左至右每個right_end指向的數與pivot比大小，若發現數字比pivot小，則代表right_end指向的數應被加入left part，所以會先將left_end+1(空出個位子給left part)，再將目前right_end指向的數與left_end做交換，這樣做直到right_end到達pivot的前一個位置結束。當partition做完後，再將pivot與right part的第一個位置做交換，來將pivot擺到left part and right part之間。接著用recursion 持兩邊都做直到無法partition。

C code solution:

int Partition(int* arr, int front, int end){
    int pivot = arr[end];
    //left part end
    int left_end = front-1;
    //right part end
    int right_end = front;
    for(; right_end<end; right_end++){
        //check if the right_end is bigger, if not change the value with the left_end
        if(arr[right_end] < pivot){
            //vacate a space for left_end
            left_end++;
            //swap value
            int tmp = arr[right_end];
            arr[right_end] = arr[left_end];
            arr[left_end] = tmp;
        }
    }
    //After the partition place the pivot in the middle
    //swap the first element of right part with pivot
    arr[end] = arr[left_end+1];
    arr[left_end+1] = pivot;
    
    //return the position of pivot
    return left_end+1;
}
void quick_sort(int* arr, int front, int end){
    //boundary
    if(!arr)
        return;
    
    //main
    if(front < end){
        int pivot = Partition(arr, front, end);
        quick_sort(arr, front, pivot-1);
        quick_sort(arr, pivot+1, end);
    }
}

Merge Sort:
採取Divide and Conquer的方式。首先有個主function merge_sort和一個副function Merge，merge_sort裡面主導主要流程，也就是先divide再merge，用recursion的方式完成。重點在Merge這個副function中，會將目前array左右兩半，做sorting並合併的動作。作法為宣告一個與input array一樣大的array tmp，然後由左至右一個一個比較left part and right part的每一個元素，較小的就往tmp上放。完成後，再將tmp的資料放進input array中。

void Merge(int* arr, int front, int mid, int end){
    //init two temp temp array
    int len = end - front + 1;
    int tmp[len];
    
    //main
    int i = front, j = mid+1, k = 0; //i==left_idx, y==right_idx, k==tmp_idx;
    //start sort
    while(i<=mid && j<=end){
        if(arr[i] < arr[j]){
            tmp[k] = arr[i];
            i++;
        }else{
            tmp[k] = arr[j];
            j++;
        }
        k++;
    }
    // sort the rest
    while(i<=mid){
        tmp[k] = arr[i];
        i++;
        k++;
    }
    while(j<=end){
        tmp[k] = arr[j];
        j++;
        k++;
    }
    
    //place the elements from tmp to arr
    for(int x=front, y=0; x<=end && y<len; x++, y++){
        arr[x] = tmp[y];
    }
}
void merge_sort(int* arr, int front, int end){
    //boundary
    if(!arr)
        return;
        
    //main
    if(front < end){
        //Divide
        int mid = (front+end)/2;
        merge_sort(arr, front, mid);
        merge_sort(arr, mid+1, end);
        //Merge
        Merge(arr, front, mid, end);
    }
}

Reference:
http://notepad.yehyeh.net/Content/Algorithm/Sort/Sort.php
http://alrightchiu.github.io/SecondRound/pages/about.html