Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- *Christophe
- *de Carvalho Pereira Martins
- *2103
- *creation : 16/11/10
- *
- * Heap sort
- */
- #include <stdio.h>
- #include <stdlib.h>
- #define MAX 19
- /*prototype*/
- void paterner(short *pVec, short inf,short sup);
- void printVec(short *pVec, short taille);
- void main(void)
- {
- short vec[MAX] = {17,45,12,22,4,86,64,66,1,43,20,35,8,10,32,25,5,15,99};
- short inf;/*indice du pere*/
- short sup;/*nbr Element du vec*/
- short temp;
- printf("Début du tri\n");
- /*mise en place du plus grand élément au debut du vecteur*/
- /*inf dernier pere*/
- if(MAX%2 == 0)
- inf = (MAX-1)/2;
- else
- inf = (MAX-2)/2;
- while(inf >= 0)
- {
- paterner(&vec[0],inf,MAX);
- inf--;
- }
- /*on parcour jusqu'a ce qu'il reste 2 case dans le vecteur donc jusque >1*/
- for(sup = MAX-1; sup > 1; sup--)
- {
- /*on permute le 1er et le dernier élément*/
- temp = vec[0];
- vec[0] = vec[sup];
- vec[sup] = temp;
- /*racine plus grand que ses 2 fils*/
- paterner(&vec[0],0,sup-1);
- }
- printf("Fin du tri\nAffichage vecteur trie\n");
- printVec(vec,MAX);
- printf("\n");
- }
- void paterner(short *pVec, short inf,short sup)
- {
- short iPere = inf;
- short iFils = (inf*2)+1;
- short temp = *(pVec+iPere);
- while(iFils < sup)
- {
- /*selection du + grand des 2 fils*/
- if(iFils < sup && *(pVec+(iFils+1)) > *(pVec+iFils))
- iFils++;
- /*temp permet de faire remonter un nombre le long d'une branche qui a déja été triée*/
- if(*(pVec+iFils) > temp)
- {
- *(pVec+iPere) = *(pVec+iFils);
- iPere = iFils;
- iFils = (iPere*2)+1;
- }
- else
- {
- /*forcage de boucle*/
- iFils = sup;
- }
- }
- *(pVec+iPere) = temp;
- }
- void printVec(short *pVec, short taille)
- {
- short i;
- for(i=0; i<taille; i++ , pVec++)
- {
- printf("%hd\t",*pVec);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement