#include <iostream>
#include <conio.h>

using namespace std;


void PrintArray(int* array, int n);
void QuickSort(int* array, int startIndex, int endIndex);
int SplitArray(int* array, int pivotValue, int indexPivot, int startIndex, int endIndex);
void swap(int &a, int &b);

int comparisons = 0;

int main(void)
{
    int array[10000];
    int i;
    FILE *file;
    file = fopen("file.txt", "r");

    for( i = 0; i < 10000; i++)
    {
         fscanf(file, "%d", &array[i]);
    }

    QuickSort(array, 0, 10000 - 1);
    PrintArray(array, 10000);
    printf("%d ", comparisons);

    getch();
    return 0;
}

void swap(int &a, int &b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}


void PrintArray(int* array, int n)
{
    int i;
    FILE *out;
    out=fopen("out.txt", "w");

    for( i = 0; i < n; i++)
        fprintf(out, "\n %d ", array[i]);
}

int choosePivot(int *array, int startIndex, int endIndex)
{
    int middle = 0;
    middle = array[(endIndex - startIndex - 1)/2 + startIndex];
    startIndex = array[startIndex];
    endIndex = array[endIndex];
    if((middle < startIndex && startIndex < endIndex) || (endIndex < startIndex && startIndex < middle))
        return startIndex;
    else
        if((startIndex < endIndex && endIndex < middle) || (middle < endIndex && endIndex < startIndex))
            return endIndex;
        else
            return middle;
}

int SplitArray(int* array, int pivot, int indexPivot, int startIndex, int endIndex)
{
    int leftBoundary = startIndex;
    int rightBoundary = endIndex;

    int i = leftBoundary + 1;

    for (int j = leftBoundary + 1; j <= rightBoundary; j++)
    {
        if (array[j] < pivot)
        {
            swap (array[j], array[i]);
            i++;
        }
        comparisons++;
    }

    swap (array[leftBoundary], array[i-1]);
    indexPivot = i-1;
    return indexPivot;

}

void QuickSort(int* array, int startIndex, int endIndex)
{
    int pivot = choosePivot(array, startIndex, endIndex);
    int splitPoint = 0, middle = 0;

    middle = (endIndex - startIndex - 1) / 2 + startIndex;

    if(endIndex > startIndex)
    {
        if(pivot == array[startIndex])
        {
            int indexPivot = startIndex;
            splitPoint = SplitArray(array, pivot, indexPivot, startIndex, endIndex);
        }
        if(pivot == array[endIndex])
        {
            int indexPivot = endIndex;
            swap(array[startIndex], array[endIndex]);
            splitPoint = SplitArray(array, pivot, indexPivot, startIndex, endIndex);
        }
        if(pivot == array[middle])
        {
            int indexPivot = (endIndex - startIndex - 1) / 2 + startIndex;
            swap(array[startIndex], array[middle]);
            splitPoint = SplitArray(array, pivot, indexPivot, startIndex, endIndex);
        }
        QuickSort(array, startIndex, splitPoint-1);
        QuickSort(array, splitPoint+1, endIndex);
    }
}