#include <iostream>
using namespace std;

const int MAX = 100;

void bubSort(int a[], int size)
{
    bool run = true;
    while (run) {
        run = false;
        for (int i = 0; i < size; i++) {
            if (a[i] > a[i + 1])
                swap (a[i], a[i + 1]);
            run = true;
        }
        size--;
    }
}

void selSort(int a[], int size)
{
    for (int i = 0; i < size - 1; i++) {
        int min = i;
        for (int j = i + 1; j < size; j++)
            if (a[j] < a[min]) min = j;
        if (i != min) swap(a[i], a[min]);
    }
}

void insSort(int a[], int size)
{
    for (int i = 1; i < size; i++) {
        int j = i, e = a[j];
        while (j > 0 && (e < a[j - 1])) {
            a[j] = a[j - 1];
            j--;
        }
        swap(e, a[j]);
    }
}

void mergeSort(int a[], int size)
{
    if (size < 20)
        insSort(a, size);
    else
    {
        
    }
}

void quickSort(int a[], int left, int right)
{
    int lo = left, hi = right, pvt = (lo + hi) / 2;
    
    while (lo <= hi) {
        while (a[lo] < a[pvt]) lo++;
        while (a[hi] > a[pvt]) hi--;
        if (lo <= hi) swap(a[lo++], a[hi--]);
    }
    if (left < hi)  quickSort(a, left, hi);
    if (right > lo) quickSort(a, right, lo);
}

void swap(int* a, int* b)        { int t; t = *a; *a = *b; *b = t; }
void fillArr(int a[], int size)  { for (int i = 0; i < size; i++) a[i] = size - i; }
void printArr(int a[], int size) { for (int i = 0; i < size; i++) cout << a[i] << endl; }

int main() 
{
    cout << "Sort Test" << endl;
    cout << "---------" << endl;
    
    int a[MAX];
    fillArr(a, MAX);
    //bubSort(a, MAX);
    //selSort(a, MAX);
    //insSort(a, MAX);
    quickSort(a, 0, MAX);
    printArr(a, MAX);
    return 0;
}