// Heapsort Algorithm
// M.Menault 2024

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

void print_array(int* array, int length)
{
    static int count = 0;
    int i = 0;
    printf("(%3.3d) Array : ",count++);
    for(i=0; i < length; i++)
    {
        printf("%5d ",array[i]);
    }
    printf("\n");
}

void sift(int* array, int node, int length)
{
    int largest_node = node;
    int left_node = 2*node+1;
    int right_node = 2*node+2;
    int temp_value = 0;

    if(left_node < length && array[left_node] > array[largest_node])
    {
        largest_node = left_node;
    }

    if(right_node < length && array[right_node] > array[largest_node])
    {
        largest_node = right_node;
    }

    if(largest_node != node)
    {
        temp_value = array[node];
        array[node] = array[largest_node];
        array[largest_node] = temp_value;
        sift(array,length,largest_node);
    }
}
 
void heapsort(int* array, int length)
{
    int i = 0;
    int temp_value = 0;
 
    // Sift the current array (binary tree)
    for(i=(length/2); i >= 0; i--)
    {
        sift(array,i,length);
    }
    // Heapsort !
    for(i=length-1; i > 0; i--)
    {
        temp_value = array[i];
        array[i] = array[0];
        array[0] = temp_value;
        sift(array,0,i);
    }
}
 
void generate_array(int* array, int length)
{
    int i = 0;
    static int first_call = 1;

    if(first_call)
    {
	first_call = 0;
        srand(time(NULL));
    }
    for(i=0; i < length; i++)
    {
        array[i] = rand() % 20 + 1;
    }
}




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

int partitionner(int T[], int premier, int dernier, int pivot) {
    echanger(&T[pivot], &T[dernier]);  // Échanger le pivot avec le dernier élément
    int j = premier;
    
    for (int i = premier; i < dernier; i++) {
        if (T[i] <= T[dernier]) {
            echanger(&T[i], &T[j]);
            j++;
        }
    }

    echanger(&T[dernier], &T[j]);  // Placer le pivot à sa position finale
    return j;
}

int choix_pivot(int T[], int premier, int dernier) {
    // Pour simplifier, on choisit simplement le dernier élément comme pivot
    return dernier;
}

void tri_rapide(int T[], int premier, int dernier) {
    if (premier < dernier) {
        int pivot = choix_pivot(T, premier, dernier);
        pivot = partitionner(T, premier, dernier, pivot);
        tri_rapide(T, premier, pivot - 1);
        tri_rapide(T, pivot + 1, dernier);
    }
}