Advertisement
Guest User

Untitled

a guest
Jul 20th, 2017
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.85 KB | None | 0 0
  1. /*
  2.  *Christophe
  3.  *de Carvalho Pereira Martins
  4.  *2103
  5.  *creation : 16/11/10
  6.  *
  7.  * Heap sort
  8.  */
  9.  
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12.  
  13. #define MAX 19
  14.  
  15. /*prototype*/
  16. void paterner(short *pVec, short inf,short sup);
  17. void printVec(short *pVec, short taille);
  18.  
  19. void main(void)
  20. {
  21.     short vec[MAX] = {17,45,12,22,4,86,64,66,1,43,20,35,8,10,32,25,5,15,99};
  22.     short inf;/*indice du pere*/
  23.     short sup;/*nbr Element du vec*/
  24.     short temp;
  25.  
  26.     printf("Début du tri\n");
  27.     /*mise en place du plus grand élément au debut du vecteur*/
  28.     /*inf dernier pere*/
  29.     if(MAX%2 == 0)
  30.         inf = (MAX-1)/2;
  31.     else
  32.         inf = (MAX-2)/2;
  33.    while(inf >= 0)
  34.    {
  35.         paterner(&vec[0],inf,MAX);
  36.         inf--;
  37.    }
  38.    
  39.     /*on parcour jusqu'a ce qu'il reste 2 case dans le vecteur donc jusque >1*/
  40.     for(sup = MAX-1; sup > 1; sup--)
  41.     {
  42.         /*on permute le 1er et le dernier élément*/
  43.         temp = vec[0];
  44.         vec[0] = vec[sup];
  45.         vec[sup] = temp;
  46.         /*racine plus grand que ses 2 fils*/
  47.         paterner(&vec[0],0,sup-1);
  48.     }
  49.  
  50.     printf("Fin du tri\nAffichage vecteur trie\n");
  51.     printVec(vec,MAX);
  52.     printf("\n");
  53. }
  54.    
  55. void paterner(short *pVec, short inf,short sup)
  56. {
  57.     short iPere = inf;
  58.     short iFils = (inf*2)+1;
  59.     short temp = *(pVec+iPere);
  60.  
  61.     while(iFils < sup)
  62.     {
  63.         /*selection du + grand des 2 fils*/
  64.         if(iFils < sup && *(pVec+(iFils+1)) > *(pVec+iFils))
  65.             iFils++;
  66.        
  67.         /*temp permet de faire remonter un nombre le long d'une branche qui a déja été triée*/
  68.         if(*(pVec+iFils) > temp)
  69.         {
  70.             *(pVec+iPere) = *(pVec+iFils);
  71.             iPere = iFils;
  72.             iFils = (iPere*2)+1;
  73.         }
  74.         else
  75.         {
  76.             /*forcage de boucle*/
  77.             iFils = sup;
  78.         }
  79.     }
  80.     *(pVec+iPere) = temp;
  81. }
  82.  
  83. void printVec(short *pVec, short taille)
  84. {
  85.     short i;
  86.  
  87.     for(i=0; i<taille; i++ , pVec++)
  88.     {
  89.         printf("%hd\t",*pVec);
  90.     }
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement