TD1_DEV51_Qualite_Algo/heapsort.c

81 lines
1.5 KiB
C
Raw Permalink Normal View History

// 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;
}
}