Heap sort
Posté : dim. sept. 08, 2024 5:52 pm
Code : Tout sélectionner
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void heapify(char* arr[], int n, int i) {
int largest = i;
int left = 2*i + 1;
int right = 2*i + 2;
if (left < n && strcmp(arr[left], arr[largest]) > 0)
largest = left;
if (right < n && strcmp(arr[right], arr[largest]) > 0)
largest = right;
if (largest != i) {
char* swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
void heapSort(char* arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i=n-1; i>=0; i--) {
char* swap = arr[0];
arr[0] = arr[i];
arr[i] = swap;
heapify(arr, i, 0);
}
}
int main() {
char* arr[] = {"banane", "cerise", "abricot", "poire", "orange","cacahuete"};
int n = sizeof(arr)/sizeof(arr[0]);
heapSort(arr, n);
for (int i=0; i<n; i++)
printf("%s\n", arr[i]);
return 0;
}