#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define NUM 9  // array length for sorting
#define MAX 27  // max number in the array

int list[NUM];
void display();
void bubbleSort();
void insertionSort();
void selectionSort();
void mergeSort();
void shellSort();
void quickSort();
void heapSort();

int main()
{
    for (int i = 0; i < NUM; i++) {
        list[i] = rand() % MAX;
    }
    printf("Input: \n");
    display();
    printf("\n");

    // bubbleSort();
    // insertionSort();
    // selectionSort();
    mergeSort();
    // shellSort();
    // quickSort();
    // heapSort();
    printf("Output: \n");
    display();
}

void display()
{
    // navigate througt all numbers
    for (int i = 0; i < NUM; i++) {
        printf("%2d ", list[i]);
        for (int j = 0; j < list[i]; j++) {
            printf("*");
        }
        printf("\n");
    }
}

void bubbleSort()
{
    int i, j, temp;
    bool swapped = false;

    // loop through all numbers
    for (i = 0; i < NUM-1; i++) {
        swapped = false;

        // loop through numbers falling ahead
        for (j = 0; j < NUM-1-i; j++) {
            // check if next number is less than current number
            // swap the numbers (bubble up)
            if (list[j] > list[j+1]) {
                temp = list[j];
                list[j] = list[j+1];
                list[j+1] = temp;
                swapped = true;
            } else {
                swapped = true;
            }
            // if no numbers was swapped that means array is sorted
            if (!swapped) {
                break;
            }
        }
        // print the sorting process
        printf("Iteration #%d: \n", i+1);
        display();
        printf("\n");
    }
}

void insertionSort()
{
    int i, valueToInsert, holePosition;

    // loop through all numbers
    for (i = 0; i < NUM; i++) {
        // select the value to be inserted
        valueToInsert = list[i];
        // select the hole position where the number is to be inserted
        holePosition = i;

        // check if previous number is larger than the number to be inserted
        while (holePosition > 0 && list[holePosition-1] > valueToInsert) {
            list[holePosition] = list[holePosition-1];
            holePosition--;
        }
        if (holePosition != i) {
            list[holePosition] = valueToInsert;
        }
        // print the sorting process
        printf("Iteration #%d: \n", i+1);
        display();
        printf("\n");
    }
}

void selectionSort()
{
    int i, j, indexMin, temp;

    // loop through all numbers
    for (i = 0; i < NUM-1; i++) {
        // set current number as minimum
        indexMin = i;
        // check the number is the minimum
        for (j = i+1; j < NUM; j++) {
            if (list[j] < list[indexMin]) {
                indexMin = j;
            }
        }

        if (indexMin != i) {
            temp = list[indexMin];
            list[indexMin] = list[i];
            list[i] = temp;
        }
        // print the sorting process
        printf("Iteration #%d: \n", i+1);
        display();
        printf("\n");
    }
}

void mergeSort()
{
    void merging(int left, int mid, int right) {
        int size = right - left + 1;
        int temp[size];
        int i, l1, l2;
        for (l1 = left, l2 = mid + 1, i = left; l1 <= mid && l2 <= right; i++) {
            if (list[l1] <= list[l2])
                temp[i] = list[l1++];
            else
                temp[i] = list[l2++];
        }
        while (l1 <= mid)
            temp[i++] = list[l1++];
        while (l2 <= right)
            temp[i++] = list[l2++];
        for (i = left; i <= right; i++)
            list[i] = temp[i];
        // print the sorting process
        display();
        printf("\n");
    }
    void sort(int left, int right) {
        int mid;
        if (left < right) {
            mid = (left + right) / 2;
            printf("sort: %d %d sort: %d %d \n", left, mid, mid+1, right);
            sort(left, mid);
            sort(mid+1, right);
            printf("mergeing: %d %d %d \n", left, mid, right);
            merging(left, mid, right);
        }
    }
    sort(0, NUM-1);
}

void shellSort()
{
    int i = 0, inner, outer, valueToInsert, interval = 1;
    while (interval < NUM/3) {
        interval = interval*3 + 1;
    }
    while (interval > 0) {
        // print sorting process
        // display();

        for (outer = interval; outer < NUM; outer++) {
            valueToInsert = list[outer];
            inner = outer;
            while (inner > interval - 1 && list[inner - interval] >= valueToInsert) {
                list[inner] = list[inner - interval];
                inner -= interval;
            }
            list[inner] = valueToInsert;
        }
        interval = (interval - 1) / 3;
        i++;
    }
}

void quickSort()
{
    void swap(int num1, int num2) {
        int temp = list[num1];
        list[num1] = list[num2];
        list[num2] = temp;
    }
    int partition(int left, int right, int pivot) {
        int leftPointer = left -1;
        int rightPointer = right;

        while (true) {
            while(list[++leftPointer] < pivot) {}
            while(rightPointer > 0 && list[--rightPointer] > pivot) {}
            if (leftPointer >= rightPointer) {
                break;
            } else {
                swap(leftPointer, rightPointer);
            }
        }

        swap(leftPointer, right);
        // print sorting process
        // display();
        return leftPointer;
    }
    void sorting(int left, int right) {
        if (right-left <= 0) {
            return;
        } else {
            int pivot = list[right];
            int partitionPoint = partition(left, right, pivot);
            sorting(left, partitionPoint - 1);
            sorting(partitionPoint + 1, right);
        }
    }
    sorting(0, NUM-1);
}

void heapSort()
{
    void heapify(int a[], int n) {
        int i, j, k, item;
        for (k = 1; k < n; k++) {
            item = a[k];
            i = k;
            j = (i-1)/2;
            while (i > 0 && item > a[j]) {
                a[i] = a[j];
                i = j;
                j = (i-1)/2;
            }
            a[i] = item;
        }
    }
    void adjust(int a[], int n) {
        int i, j, item;
        j = 0;
        item = a[j];
        i = 2*j + 1;
        while (i <= n-1) {
            if (i+1 <= n-1) {
                if (a[i] < a[i+1]) {
                    i++;
                }
            }
            if (item < a[i]) {
                a[j] = a[i];
                j = i;
                i = 2*j +1;
            } else {
                break;
            }
        }
        a[j] = item;
    }
    void sorting(int a[], int n) {
        int i, t;
        heapify(a, n);
        for (i = n - 1; i > 0; i--) {
            t = a[0];
            a[0] = a [i];
            a[i] = t;
            adjust(a, i);
        }
    }
    sorting(list, NUM);
}