using namespace std;

#define SELECTSORT      1
#define INSERTSORT      1
#define BUBBLESORT      1
#define SHELLSORT       1
#define QUICKSORT       1
#define MERGESORT       1

template<typename T>
void print(T array[], int len)
{
    for (int i=0; i<len; i++) {
        cout<<array[i]<<" ";   
    }
    cout<<endl;
}

template<typename T>
void Swap(T& a, T& b)
{
    T temp = a;
    a = b;
    b = temp;   
}

#ifdef SELECTSORT
template<typename T>
void SelectSort(T array[], int len)
{
    int i = 0;
    int j = 0;
    int k = -1;

    for (i=0; i<len; i++) {
        k = i;
        for (j=i+1; j<len; j++) {
            if (array[j] < array[k]) {
                k = j;   
            }   
        } 

        if (k != i) {
            swap(array[i], array[k]); 
        }
    }   
}
#endif

#ifdef INSERTSORT
template<typename T>
void InsertSort(T array[], int len)
{
    int i = 0;
    int j = 0;
    int k = -1;
    int temp = -1;

    for (i=1; i<len; i++) {
        k = i;
        temp = array[k];

        for (j=i-1; (j>=0)&&(array[j]>temp); j--) {
            array[j+1] = array[j];
            k = j;
        }   

        array[k] = temp;
    }   
}
#endif

#ifdef BUBBLESORT
template<typename T>
void BubbleSort(T array[], int len)
{
    int i = 0;
    int j = 0;
    int exchange = 1;

    for (i=0; i<len && exchange; i++) {
        exchange = 0;
        for (j=len-1; j>0; j--) {
            if (array[j] < array[j-1]) {
                Swap(array[j], array[j-1]);
                exchange = 1;
            }   
        }   
    }   
}
#endif

#ifdef SHELLSORT
template<typename T>
void ShellSort(T array[], int len)
{
    int i = 0;
    int j = 0;
    int k = 0;
    int temp = 0;
    int gap = len;

    do {
        gap = gap / 3 + 1;

        for (i=gap; i<len; i+=gap) {
            k = i;
            temp = array[k];

            for (j=i-gap; j>=0&&array[j]>temp; j-=gap) {
                array[j+gap] = array[j];
                k = j;   
            }

            array[k] = temp;   
        }
    } while (gap > 1);
}
#endif

#ifdef QUICKSORT
template<typename T>
int parition(T array[], int low, int high)
{
    int pv = array[low];

    while (low < high) {
        while ((low<high) && (array[high] >= pv)) {
            high--;   
        }   

        Swap(array[low], array[high]);

        while ((low<high) && (array[low] <= pv)) {
            low++;   
        }

        Swap(array[low], array[high]);
    }

    return low;
}

template<typename T>
void QSort(T array[], int low, int high)
{
    if (low < high) {
        int part = parition(array, low, high);
        QSort(array, low, part-1);   //可以理解為左邊數列
        QSort(array, part+1, high);  //可以理解為右邊數列  
    }   
}

template<typename T>
void QuickSort(T array[], int len)
{
    QSort(array, 0, len-1);       
}
#endif

#ifdef MERGESORT
template<typename T>
void Merge(T src[], T des[], int low, int mid, int high)
{
    int i = low;
    int j = mid+1;
    int k = low;

    while (i<=mid && j<=high) {
        if (src[i] < src[j]) {
            des[k++] = src[i++];   
        } else {
            des[k++] = src[j++];   
        }
    } 

    while (i<=mid) {
        des[k++] = src[i++];   
    } 

    while (j<=high) {
        des[k++] = src[j++];   
    }
}

template<typename T>
void MSort(T src[], T des[], int low, int high, int max)
{
    if (low == high) {
        des[low] = src[low];   
    } else {
        int mid = (low + high) / 2;

        T *space = (T *)malloc(sizeof(T)*max);

        if (space != NULL) {
            MSort(src, space, low, mid, max);
            MSort(src, space, mid+1, high, max); 

            Merge(space, des, low, mid, high);
        }

        free(space);
        space = NULL;
    }     
}

template<typename T>
void MergeSort(T array[], int len)
{
    MSort(array, array, 0, len-1, len);
}
#endif