# Different Sorting Time Test:
## Insertion sort, Counting sort, Merge sort, and Quick sort ( Lomuto, Hoare, Three way Partition )

程式碼:

#include<iostream>
#include<vector>
#include<time.h>
#include<algorithm>
using namespace std;

enum type{
    Lomuto = 0, Hoare, Three_Way
};

static int partition_Type = 0;

const int Max = 1000;

void printArray(vector<int> &arr, int n);

void insertionSort(vector<int> &arr, int n)
{
    int i, key, j;
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;

        // Move elements of arr[0..i-1],
        // that are greater than key, to one
        // position ahead of their
        // current position
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

void Merge(std::vector<int> &Array, int front, int mid, int end){

    // 利用 std::vector 的constructor,
    // 把array[front]~array[mid]放進 LeftSub[]
    // 把array[mid+1]~array[end]放進 RightSub[]
    std::vector<int> LeftSub(Array.begin()+front, Array.begin()+mid+1),
                     RightSub(Array.begin()+mid+1, Array.begin()+end+1);

    LeftSub.insert(LeftSub.end(), Max);      // 在LeftSub[]尾端加入值為 Max 的元素
    RightSub.insert(RightSub.end(), Max);    // 在RightSub[]尾端加入值為 Max 的元素

    int idxLeft = 0, idxRight = 0;

    for (int i = front; i <= end; i++) {

        if (LeftSub[idxLeft] <= RightSub[idxRight] ) {
            Array[i] = LeftSub[idxLeft];
            idxLeft++;
        }
        else{
            Array[i] = RightSub[idxRight];
            idxRight++;
        }
    }
}

void MergeSort(std::vector<int> &array, int front, int end){
                                         // front與end為矩陣範圍
    if (front < end) {                   // 表示目前的矩陣範圍是有效的
        int mid = (front+end)/2;         // mid即是將矩陣對半分的index
        MergeSort(array, front, mid);    // 繼續divide矩陣的前半段subarray
        MergeSort(array, mid+1, end);    // 繼續divide矩陣的後半段subarray
        Merge(array, front, mid, end);   // 將兩個subarray做比較, 並合併出排序後的矩陣
    }
}

void countSort(vector<int>& arr)
{
    int max = *max_element(arr.begin(), arr.end());
    int min = *min_element(arr.begin(), arr.end());
    int range = max - min + 1;

    vector<int> count(range), output(arr.size());
    for (int i = 0; i < arr.size(); i++)
        count[arr[i] - min]++;

    for (int i = 1; i < count.size(); i++)
        count[i] += count[i - 1];

    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }

    for (int i = 0; i < arr.size(); i++)
        arr[i] = output[i];
}

int Lomuto_partition(vector<int> &arr, int low, int high);

int Hoare_partition(vector<int> &arr, int low, int high);

void Three_Way_partition(vector<int> &arr, int l, int r, int& i, int& j);


void quickSort(vector<int> &arr, int low, int high)
{
    if (low < high)
    {

        ///Lomuto partition
        if(partition_Type == Lomuto){
            /* pi is partitioning index, arr[p] is now
                at right place */
            int pi = Lomuto_partition(arr, low, high);

            // Separately sort elements before
            // partition and after partition
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
        ///Hoare partition
        else if(partition_Type == Hoare){
            /* pi is partitioning index, arr[p] is now
                at right place */
            int pi = Hoare_partition(arr, low, high);


            // Separately sort elements before
            // partition and after partition
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
        ///Three way partition
        else if(partition_Type == Three_Way){
            /* i,j is partitioning index, arr[p] is now
                at right place */
            int i, j;

            // Note that i and j are passed as reference
            Three_Way_partition(arr, low, high, i, j);


            // Separately sort elements before
            // partition and after partition
            quickSort(arr, low, j);
            quickSort(arr, i, high);
        }


    }
}

int Lomuto_partition(vector<int> &arr, int low, int high)
{
    int pivot = arr[high];    // pivot
    int i = (low - 1);  // Index of smaller element

    for (int j = low; j <= high- 1; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            i++;    // increment index of smaller element
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

int Hoare_partition(vector<int> &arr, int low, int high)
{
    int pivot = arr[low];
    int i = low - 1, j = high + 1;

    while (true) {
        // Find leftmost element greater than
        // or equal to pivot
        do {
            i++;
        } while (arr[i] < pivot);

        // Find rightmost element smaller than
        // or equal to pivot
        do {
            j--;
        } while (arr[j] > pivot);

        // If two pointers met.
        if (i >= j)
            return j;

        swap(arr[i], arr[j]);
    }
}

void Three_Way_partition(vector<int> &arr, int l, int r, int& i, int& j)
{
    i = l - 1, j = r;
    int p = l - 1, q = r;
    int v = arr[r];

    while (true) {
        // From left, find the first element greater than
        // or equal to v. This loop will definitely
        // terminate as v is last element
        while (arr[++i] < v)
            ;

        // From right, find the first element smaller than
        // or equal to v
        while (v < arr[--j])
            if (j == l)
                break;

        // If i and j cross, then we are done
        if (i >= j)
            break;

        // Swap, so that smaller goes on left greater goes
        // on right
        swap(arr[i], arr[j]);

        // Move all same left occurrence of pivot to
        // beginning of array and keep count using p
        if (arr[i] == v) {
            p++;
            swap(arr[p], arr[i]);
        }

        // Move all same right occurrence of pivot to end of
        // array and keep count using q
        if (arr[j] == v) {
            q--;
            swap(arr[j], arr[q]);
        }
    }

    // Move pivot element to its correct index
    swap(arr[i], arr[r]);

    // Move all left same occurrences from beginning
    // to adjacent to arr[i]
    j = i - 1;
    for (int k = l; k < p; k++, j--)
        swap(arr[k], arr[j]);

    // Move all right same occurrences from end
    // to adjacent to arr[i]
    i = i + 1;
    for (int k = r - 1; k > q; k--, i++)
        swap(arr[i], arr[k]);
}

int main(){
    int power_of_2;
    do {
        cout<<"Enter a number(0~20)"<<endl;
        cin>>power_of_2;
    }while(power_of_2>30);

    unsigned int num = 1<<power_of_2;

    cout<<power_of_2<<": "<<num<<endl;

    vector<int> vec[10];

    for(int i=0 ; i<10 ; ++i){
        int countn = num;
        while(countn--){
            int temp = rand()%1000;
            vec[i].push_back(temp);
        }
    }

    clock_t start_t, end_t, average = 0;

    for(int i =0 ; i<10 ; ++i){
        start_t = clock();
        //insertionSort(vec[i],num);
        //MergeSort(vec[i], 0, num-1);
        //countSort(vec[i]);

        {
            //partition_Type = Lomuto;
            //partition_Type = Hoare;
            partition_Type = Three_Way;

            quickSort(vec[i], 0, num-1);
        }


        end_t = clock();
        average+=(end_t-start_t);
    }

    if(power_of_2<=10){
        for(int i =0 ; i<10 ; ++i){
            printArray(vec[i],num);
        }
    }

    cout<<average/10.0<<"ms"<<endl;

}

// A utility function to print an array
// of size n
void printArray(vector<int> &arr, int n)
{
    int i;
    for (i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}