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

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

int * selectionSort(int * arr, size_t n)
{
    int tmp = 0;
    for (int i = 0; i < (int)n - 1; i++)
    {
        int position = i;
        for (int j = i + 1; j < (int)n; j++)
            if ( arr[position] > arr[j])
                position = j;
        if (position != i)
            swap(&arr[position], &arr[j]);
    }

    return arr;
}

void heapify(int * arr, size_t n, int i)
{
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[smallest])
        smallest = left;
    if (right < n && arr[right] > arr[smallest])
        smallest = right;

    if (smallest != i)
    {
        swap(&arr[i], &arr[smallest]);
        heapify(arr,n,smallest);
    }
}

int * heapSort(int * arr, size_t n)
{
    for (int i = n/2 - 1; i >= 0; i--)
        heapify(arr,n,i);

    for (int i = n - 1; i >= 0; i--)
    {
        swap(&arr[i],&arr[0]);
        heapify(arr,i,0);
    }

    return arr;
}

int main(void)
{
    int sarr[] = {12,63,58,95,41,35,65,0,38,44};
    int harr[] = {12,63,58,95,41,35,65,0,38,44};
    size_t size = sizeof(sarr)/sizeof(int);


    printf("Before sort:\n");
    for (int i = 0; i < (int)size; i++)
        printf("%3d",sarr[i]);
    putchar('\n');

    selectionSort(sarr,size);
    printf("After selection sort:\n");
    for (int i = 0; i < (int)size; i++)
        printf("%3d",sarr[i]);
    putchar('\n');

    heapSort(harr,size);
    printf("After heap sort:\n");
    for (int i = 0; i < (int)size; i++)
        printf("%3d",harr[i]);
    putchar('\n');

    return 0;
}