annonce 1

Bandeau publicitaire haut

mercredi 8 février 2012

i finaly find out....


Today, teacher ask as to code "Heapsort" for tomorrow...
after a lot of research, i've found a lot of logarythme, but no one could be understable, so... after a lot of test, i've finaly made this code, feel free to test at home for thoses who understand this (and could understand my english :D)


#include <stdio.h>
#include <stdlib.h>
#define N 18

void heap_sort(int tab[], int n);
void paterner (int tab[], int inf, int sup);
void echange (int *t1, int *t2 );

int main()
{
int tab[18]={17,45,12,22,4,86,64,66,1,43,20,35,8,10,32,25,5,15};
int n=18;
int i;

printf("\nVoici le tableau de depart non trie=>\n");
for (i=0;i<n;i++)
printf("%3d",tab[i]);

heap_sort(tab,n);

printf("\n\nVoici le tableau trie=>\n");
for (i=0;i<N;i++)
printf("%3d",tab[i]);

return 0;
}

void heap_sort(int tab[], int n)
{
int i,j,cmp=0, nbr, tamere=0;

for (i=n/2-1;i>=0;i--)
{
paterner(tab,i,n-1);

printf("\n\nVoici le tas:%d\n",cmp);
cmp++;
for (j=0;j<n;j++)
printf("%3d",tab[j]);
}
for(nbr=n-1;nbr>=1;nbr--)
{
echange(&tab[0],&tab[nbr]);
paterner(&tab[0],0,nbr-1);

printf("\n\nVoici le tri:%d\n",tamere);
tamere++;
for (j=0;j<n;j++)
printf("%3d",tab[j]);
}
}

void echange(int *num1, int *num2)
{
int temp;

temp=*num1;
*num1=*num2;
*num2=temp;
}

void paterner(int tab[],int inf, int sup)
{
int ipere=inf;
int ifils=(ipere*2)+1;
while(ifils<=sup)
{
if (ifils<sup && tab[ifils+1]>tab[ifils])
{
ifils=ifils+1;
}
if (tab[ifils]>tab[ipere])
{
echange(&tab[ipere], &tab[ifils]);
ipere=ifils;
ifils=(ipere*2)+1;
}
else
{
break;
}
}

}

5 commentaires: