#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int *a, int *b);
void init_array(int *arr, int length);
void dump(int *arr, int length);
void bubble_sort(int *arr, int length);
int partion(int *arr, int start, int end);
void quick_sort(int *arr, int start, int end);
void select_sort(int *arr, int length);
void insert_sort(int *arr, int length);
void heap_adjust(int *arr, int index, int length);
void heap_sort(int *arr, int length);
void merge(int *arr, int low, int mid, int high);
void merge_sort(int *arr, int low, int high);
void shell_sort(int *arr, int length);

int main() {
    int length = 100;
    int *arr = (int *) malloc (length);

    printf("bubble sort:\n");
    init_array(arr, length);
    dump(arr, length);
    bubble_sort(arr, length);
    dump(arr, length);

    printf("\nquick sort:\n");
    init_array(arr, length);
    dump(arr, length);
    quick_sort(arr, 0, length - 1);
    dump(arr, length);

    printf("\nselect sort:\n");
    init_array(arr, length);
    dump(arr, length);
    select_sort(arr, length);
    dump(arr, length);

    printf("\ninsert sort:\n");
    init_array(arr, length);
    dump(arr, length);
    insert_sort(arr, length);
    dump(arr, length);

    printf("\nheap sort:\n");
    init_array(arr, length);
    dump(arr, length);
    heap_sort(arr, length);
    dump(arr, length);

    printf("\nmerge sort:\n");
    init_array(arr, length);
    dump(arr, length);
    merge_sort(arr, 0, length);
    dump(arr, length);

    printf("\nshell sort:\n");
    init_array(arr, length);
    dump(arr, length);
    shell_sort(arr, length);
    dump(arr, length);

    return 0;
}

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

void init_array(int *arr, int length) {
    if (!arr) {
        return;
    }

    srand(time(NULL));
    int i;
    for (i = 0; i < length; i++) {
        arr[i] = rand() % (length * 10);
    }
}

void dump(int *arr, int length) {
    if (!arr) {
        return;
    }

    int i;
    for (i = 0; i < length; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void bubble_sort(int *arr, int length) {
    if (!arr) {
        return;
    }

    int i, j;
    for (i = 0; i < length; i++) {
        for (j = 0; j < length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr + j, arr + j + 1);
            }
        }
    }
}

int partion(int *arr, int start, int end) {
    int tmp = arr[start];

    while (start < end) {
        while (start < end && arr[end] >= tmp) {
            end--;
        }
        if (start < end) {
            arr[start++] = arr[end];
        }

        while (start < end && arr[start] <= tmp) {
            start++;
        }
        if (start < end) {
            arr[end--] = arr[start];
        }
    }

    arr[start] = tmp;
    return start;
}

void quick_sort(int *arr, int start, int end) {
    int index;
    if (start < end) {
        index = partion(arr, start, end);
        quick_sort(arr, start, index - 1);
        quick_sort(arr, index + 1, end);
    }
}

void select_sort(int *arr, int length) {
    int i, j;
    for (i = 0; i < length - 1; i++) {
        int index = i;
        for (j = i + 1; j < length; j++) {
            if (arr[j] < arr[index]) {
                index = j;
            }
        }

        if (index != i) {
            swap(arr + i, arr + index);
        }
    }
}

void insert_sort(int *arr, int length) {
    int i, j;
    for (i = 1; i < length; i++) {
        int tmp = arr[i];
        for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = tmp;
    }
}

void heap_adjust(int *arr, int index, int length) {
    while (2 * index + 1 < length) {
        int max_index = 2 * index + 1;
        if (2 * index + 2 < length && arr[2 * index + 1] < arr[2 * index + 2]) {
            max_index++;
        }

        if (arr[max_index] > arr[index]) {
            swap(arr + max_index, arr + index);
            index = max_index;
        } else {
            break;
        }
    }
}

void heap_sort(int *arr, int length) {
    int i;
    for (i = length / 2 - 1; i >=0; --i) {
        heap_adjust(arr, i, length);
    }

    for (i = length - 1; i > 0; i--) {
        swap(arr, arr + i);
        heap_adjust(arr, 0, i);
    }
}

void merge(int *arr, int low, int mid, int high) {
    int tmp[high - low + 1];
    int k = 0;
    int i = low;
    int j = mid;
    while (i < mid && j < high) {
        if (arr[i] < arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }

    while (i < mid) {
        tmp[k++] = arr[i++];
    }
    while (j < high) {
        tmp[k++] = arr[j++];
    }

    for (i = 0; i < k; i++) {
        arr[low + i] = tmp[i];
    }
}

void merge_sort(int *arr, int low, int high) {
    if (low + 1 < high) {
        int mid = (low + high) / 2;
        merge_sort(arr, low, mid);
        merge_sort(arr, mid, high);
        merge(arr, low, mid, high);
    }
}

void shell_sort(int *arr, int length) {
    int i, j, delta;
    int pivot;
    for (delta = length / 2; delta > 0; delta /= 2) {
        for (i = delta; i < length; i++) {
            pivot = arr[i];
            for (j = i - delta; j >= 0 && arr[j] > pivot; j -= delta) {
                arr[j + delta] = arr[j];
            }
            arr[j + delta] = pivot;
        }
    }
}