Skip to content
Snippets Groups Projects
Select Git revision
  • 0ff5c5c28576e54824805a4551619626abbb0897
  • master default protected
2 results

README.md

Blame
  • heapsort.c 1.10 KiB
    #include <stdio.h>
    #include <stdlib.h>
    #include "heapsort.h"
    
    static void swap(int* a,int* b) {
       int tmp = *a;
       *a = *b;
       *b = tmp;
    }
    
    static void print(int* tab,int size,char* str) {
       for (int i=0;i<size;i++) {
          printf("%d ",tab[i]);
       }
       printf("%s",str);
    }
    
    void heapsort(int* tab,int size) {
       entassement(tab,size);
       swap(tab,tab+size-1);
       for (int s=size-1;s>1;s--) {
          promotion(tab,s,0);
          swap(tab,tab+s-1);
       }
    }
    void entassement(int* tab,int size) {
       for (int i=size/2-1;i>=0;i--) {
          promotion(tab,size,i);
       }
    }
    
    void promotion(int* tab,int size,int i) {
       int ind_max = max3(tab,size,i);
       if (ind_max != i) {
          promotion(tab,size,ind_max);
       } 
    }
    
    int max3(int* tab,int size,int i) {
       int ind_max = i;
       int left = fils_g(i), right = fils_d(i);
       if (left  < size && tab[ind_max] < tab[left]) {
          ind_max = left;
       }
       if (right < size && tab[ind_max] < tab[right]) {
          ind_max = right;
       }
       if (i != ind_max) {
          swap(tab+i,tab+ind_max);
       }
       return ind_max; 
    }
    
    int fils_g(int i) { 
       return 2*i+1; 
    }
    
    int fils_d(int i) {
       return 2*i+2; 
    }