#include "Sorting.h"

void dataInit(Data* data, int arraySize, int repeat)
{
    data->arraySize = arraySize;
    data->array = (int*)malloc(data->arraySize * sizeof(int));
}

void dataFree(Data* data)
{
    free(data->array);
}

void assignRandomValues(int* array, int arraySize)
{
    int i;
    for (i = 0; i < arraySize; i++)
        array[i] = rand() % 101;
}

void copyValues(int* sourceArray, int* arrayToCopyTo, int arraySize)
{
    int i;
    for (i = 0; i < arraySize; i++)
        arrayToCopyTo[i] = sourceArray[i];
}

void swapElementsOfArray(int* firstElement, int* secondElement)
{
    int tmp = *secondElement;
    *secondElement = *firstElement;
    *firstElement = tmp;
}

void bubbleSorting(int* array, int arraySize, int* comparisons, int* substitutions)
{
    int i, j;
    for (i = 0; i < arraySize - 1; i++)
        for (j = 0; j < arraySize - i - 1; j++)
        {
            (*comparisons)++;
            if (array[j] > array[j + 1])
            {
                swapElementsOfArray(&array[j], &array[j + 1]);
                (*substitutions) += 2;
            }
        }
}

void insertionSorting(int* array, int arraySize, int* comparisons, int* substitutions)
{
    int i, j;
    int tmp;
    for (i = 1; i < arraySize; i++)
    {
        tmp = array[i];
        j = i - 1;
        while (j >= 0 && array[j] > tmp)
        {
            (*comparisons)++;
            array[j + 1] = array[j];
            (*substitutions)++;
            j = j - 1;
        }
        array[j + 1] = tmp;
        (*substitutions)++;
    }
}

void shellSorting(int* array, int arraySize, int* comparisons, int* substitutions)
{
    int i, j, l;
    int k = 1;
    int interval = arraySize / 2;
    while (interval >= 1)
    {
        for (l = 0; l < interval; l++)
        {
            for (i = l; i < arraySize - 1; i += interval)
                for (j = l; j < arraySize - i - 1; j += interval)
                {
                    (*comparisons)++;
                    if (j + interval < arraySize)
                        if (array[j] > array[j + interval])
                        {
                            swapElementsOfArray(&array[j], &array[j + interval]);
                            (*substitutions) += 2;
                        }
                }
        }
        k++;
        interval = arraySize / pow(2.0, k);
    }
    bubbleSorting(array, arraySize, comparisons, substitutions);
}

int quickSort_Partition(int* array, int firstIndex, int lastIndex, int* comparisons, int* substitutions)
{
    int pivot = array[firstIndex];
    int i = firstIndex, j;
    for (j = firstIndex + 1; j <= lastIndex; j++)
    {
        (*comparisons)++;
        if (array[j] < pivot)
        {
            i++;
            swapElementsOfArray(&array[i], &array[j]);
            (*substitutions) += 2;
        }
    }
    swapElementsOfArray(&array[i], &array[firstIndex]);
    (*substitutions) += 2;
    return i;

}

void quickSorting(int* array, int firstIndex, int lastIndex, int* comparisons, int* substitutions)
{
    int partitioningIndex;
    if (firstIndex < lastIndex)
    {
        partitioningIndex = quickSort_Partition(array, firstIndex, lastIndex, comparisons, substitutions);
        quickSorting(array, firstIndex, partitioningIndex, comparisons, substitutions);
        quickSorting(array, partitioningIndex + 1, lastIndex, comparisons, substitutions);
    }
}

void printArray(int* array, int arraySize)
{
    int i;
    for (i = 0; i < arraySize; i++)
        printf("%d, ", array[i]);
    printf("\n\n");
}

void printArrayChar(char* array[], int arraySize)
{
    int i;
    for (i = 0; i < arraySize; i++)
        printf("%s, ", array[i]);
    printf("\n\n");
}

int getRandomSize(int approxArraySize)
{
    int x = approxArraySize / 10, result;
    result = (rand() % (2 * x)) - x;
    result += approxArraySize;
    return result;
}

void checkMinMax(Data* data, int comps, int subs)
{
    if (data->minComparisons > comps)
        data->minComparisons = comps;
    if (data->maxComparisons < comps)
        data->maxComparisons = comps;
    if (data->minSubstitutions > subs)
        data->minSubstitutions = subs;
    if (data->maxSubstitutions < subs)
        data->maxSubstitutions = subs;

    data->sumOfComparisons += (long)comps;
    data->sumOfSubstitutions += (long)subs;
}

void compareSortingAlgorithms(int sizeOfSortedArray, int numberOfRepeats)
{
    int* originalArray;
    Data bubbleSort, insertionSort, shellSort, quickSort;
    int arraySize;
    const int approxArraySize = sizeOfSortedArray;
    const int repeats = numberOfRepeats;
    int i;
    int bbSortComps = 0, insSortComps = 0, shllSortComps = 0, qckSortComps = 0;
    int bbSortSubs = 0, insSortSubs = 0, shllSortSubs = 0, qckSortSubs = 0;

    srand((int)time(NULL));

    bubbleSort.sumOfComparisons = bubbleSort.sumOfSubstitutions = insertionSort.sumOfComparisons = insertionSort.sumOfSubstitutions = shellSort.sumOfComparisons = shellSort.sumOfSubstitutions = quickSort.sumOfComparisons = quickSort.sumOfSubstitutions = 0;

    for (i = 0; i < repeats; i++)
    {
        arraySize = getRandomSize(approxArraySize);
        originalArray = (int*)malloc(arraySize * sizeof(int));
        assignRandomValues(originalArray, arraySize);

        dataInit(&bubbleSort, arraySize, i);
        dataInit(&insertionSort, arraySize, i);
        dataInit(&shellSort, arraySize, i);
        dataInit(&quickSort, arraySize, i);

        bbSortComps = insSortComps = shllSortComps = qckSortComps = 0;
        bbSortSubs = insSortSubs = shllSortSubs = qckSortSubs = 0;

        copyValues(originalArray, bubbleSort.array, bubbleSort.arraySize);
        copyValues(originalArray, insertionSort.array, insertionSort.arraySize);
        copyValues(originalArray, shellSort.array, shellSort.arraySize);
        copyValues(originalArray, quickSort.array, quickSort.arraySize);

        bubbleSorting(bubbleSort.array, bubbleSort.arraySize, &bbSortComps, &bbSortSubs);
        insertionSorting(insertionSort.array, insertionSort.arraySize, &insSortComps, &insSortSubs);
        shellSorting(shellSort.array, shellSort.arraySize, &shllSortComps, &shllSortSubs);
        quickSorting(quickSort.array, 0, quickSort.arraySize - 1U, &qckSortComps, &qckSortSubs);

        if (i == 0)
        {
            bubbleSort.minComparisons = bubbleSort.maxComparisons = bbSortComps;
            bubbleSort.minSubstitutions = bubbleSort.maxSubstitutions = bbSortSubs;
            insertionSort.minComparisons = insertionSort.maxComparisons = insSortComps;
            insertionSort.minSubstitutions = insertionSort.maxSubstitutions = insSortSubs;
            shellSort.minComparisons = shellSort.maxComparisons = shllSortComps;
            shellSort.minSubstitutions = shellSort.maxSubstitutions = shllSortSubs;
            quickSort.minComparisons = quickSort.maxComparisons = qckSortComps;
            quickSort.minSubstitutions = quickSort.maxSubstitutions = qckSortSubs;
        }
        else
        {
            checkMinMax(&bubbleSort, bbSortComps, bbSortSubs);
            checkMinMax(&insertionSort, insSortComps, insSortSubs);
            checkMinMax(&shellSort, shllSortComps, shllSortSubs);
            checkMinMax(&quickSort, qckSortComps, qckSortSubs);
        }

        dataFree(&bubbleSort);
        dataFree(&insertionSort);
        dataFree(&shellSort);
        dataFree(&quickSort);

        free(originalArray);
    }
    bubbleSort.avgComparisons = bubbleSort.sumOfComparisons / repeats;
    insertionSort.avgComparisons = insertionSort.sumOfComparisons / repeats;
    shellSort.avgComparisons = shellSort.sumOfComparisons / repeats;
    quickSort.avgComparisons = quickSort.sumOfComparisons / repeats;
    bubbleSort.avgSubstitutions = bubbleSort.sumOfSubstitutions / repeats;
    insertionSort.avgSubstitutions = insertionSort.sumOfSubstitutions / repeats;
    shellSort.avgSubstitutions = shellSort.sumOfSubstitutions / repeats;
    quickSort.avgSubstitutions = quickSort.sumOfSubstitutions / repeats;

    printf("Bubblesort:\n\tMin porownan: %d\n\tMax porownan: %d\n\tSrednia porownan: %d\n\n\tMin podstawien: %d\n\tMax podstawien: %d\n\tSrednia podstawien: %d\n\n", bubbleSort.minComparisons, bubbleSort.maxComparisons, bubbleSort.avgComparisons, bubbleSort.minSubstitutions, bubbleSort.maxSubstitutions, bubbleSort.avgSubstitutions);
    printf("Insertionsort:\n\tMin porownan: %d\n\tMax porownan: %d\n\tSrednia porownan: %d\n\n\tMin podstawien: %d\n\tMax podstawien: %d\n\tSrednia podstawien: %d\n\n", insertionSort.minComparisons, insertionSort.maxComparisons, insertionSort.avgComparisons, insertionSort.minSubstitutions, insertionSort.maxSubstitutions, insertionSort.avgSubstitutions);
    printf("Shellsort:\n\tMin porownan: %d\n\tMax porownan: %d\n\tSrednia porownan: %d\n\n\tMin podstawien: %d\n\tMax podstawien: %d\n\tSrednia podstawien: %d\n\n", shellSort.minComparisons, shellSort.maxComparisons, shellSort.avgComparisons, shellSort.minSubstitutions, shellSort.maxSubstitutions, shellSort.avgSubstitutions);
    printf("Quicksort:\n\tMin porownan: %d\n\tMax porownan: %d\n\tSrednia porownan: %d\n\n\tMin podstawien: %d\n\tMax podstawien: %d\n\tSrednia podstawien: %d\n\n", quickSort.minComparisons, quickSort.maxComparisons, quickSort.avgComparisons, quickSort.minSubstitutions, quickSort.maxSubstitutions, quickSort.avgSubstitutions);

    system("pause");
}

void Heapify(char* array[], int i, int heapSize)
{
    int left, right, largest = i;
    char* tmp;

    left = 2 * i + 1;
    right = 2 * i + 2;

    if (left < heapSize && strcmp(array[left], array[largest]) == 1)
        largest = left;

    if (right < heapSize && strcmp(array[right], array[largest]) == 1)
        largest = right;

    if (largest != i)
    {
        tmp = array[i];
        array[i] = array[largest];
        array[largest] = tmp;
        Heapify(array, largest, heapSize);
    }
}

void BuildHeap(char* array[], int size)
{
    int i;
    for (i = (size / 2) - 1; i >= 0; i--)
        Heapify(array, i, size);
}

void HeapSort(char* array[], int size)
{
    int i, heapSize = size;
    char* tmp;
    BuildHeap(array, size);
    for (i = size - 1; i >= 0; i--)
    {
        tmp = array[0];
        array[0] = array[i];
        array[i] = tmp;
        Heapify(array, 0, --heapSize);
    }
}

void HeapSortHandle()
{
    char* stringArray[] = { "Q","W","E","R","T","Y","U","I","O","P","A","S","D","F","G","H","J","K","L","Z","X","C","V","B","N","M" };

    printArrayChar(stringArray, sizeof(stringArray) / sizeof(stringArray[0]));
    HeapSort(stringArray, sizeof(stringArray) / sizeof(stringArray[0]));
    printArrayChar(stringArray, sizeof(stringArray) / sizeof(stringArray[0]));
    menuPause();

}

void CountingSort(int array[], int arraySize, int maxNaturalNumber)
{
    int i, j = 0;
    int* counterArray = (int*)calloc(maxNaturalNumber + 1, sizeof(int));
    if (counterArray != NULL)
    {
        for (i = 0; i < arraySize; i++)
            counterArray[array[i]]++;
        for (i = 0; i <= maxNaturalNumber; i++)
            while (counterArray[i]--)
                array[j++] = i;
        free(counterArray);
    }
}

void CountingSortHandle(int arraySize, int maxNaturalNumber)
{
    int* array, i;
    array = (int*)calloc(arraySize, sizeof(int));
    if (array != NULL)
        for (i = 0; i < arraySize; i++)
            array[i] = rand() % (maxNaturalNumber + 1);
    printArray(array, arraySize);
    CountingSort(array, arraySize, maxNaturalNumber);
    printArray(array, arraySize);
    menuPause();
}

void Sorting_Menu()
{
    int size, repeats;
    int option = 1;
    int i, k;
    char* programName[] =
    {
        "Wyjdz",
        "Porownanie algorytmow (BubbleSort, InsertionSort, ShellSort, QuickSort) [zadanie 21]",
        "Implementacja sortowania przez kopcowanie [zadanie 22]",
        "Implementacja sortowania przez zliczanie [zadanie 23]"
    };
    int programCount = sizeof(programName) / sizeof(programName[0]);
    while (option)
    {
        system("cls");
        for (i = 1; i < programCount; i++)
        {
            printf("%d - %s\n", i, programName[i]);
        }
        printf("0 - %s\n", programName[0]);
        printf("\nWybor:");
        scanf("%d", &option);
        switch (option)
        {
        case 1:
            printf("Podaj przyblizona wielkosc sortowanych tablicy:");
            scanf("%d", &size);
            printf("Podaj liczbe powtorzen:");
            scanf("%d", &repeats);
            compareSortingAlgorithms(size, repeats);
            break;
        case 2:
            HeapSortHandle();
            break;
        case 3:
            printf("Podaj wielkosc tablicy do posortowania:");
            scanf("%d", &size);
            printf("Podaj maksymalna wartosc k:");
            scanf("%d", &k);
            CountingSortHandle(size, k);
            break;
        case 0:
            break;
        }

    }
}