Heapsort

Télécharger le projet
Commenter

Description

C'est un des algo de tri les plus rapides (de l'ordre de nbelm log nbelm itérations) pour trier nbelm éléments.

Source / Exemple : 


#include <iostream.h>

void arranger(int,int);

//Attention, il faut prévoir la preimère case du vecteur libre
//et préciser un nombre d'éléments ne l'incluant pas.

//ICI:
//la première case = 0 pour dire qu'elle ne sert pas. Mais quelle que soit sa valeur
//elle ne sera pas prise en compte.
//le nombre d'éléments vaut 20 alors que 21 cases sont réservées
int tabint[] = {0,1,4,8,5,11,3,4,14,11,58,1,6,7,24,2,6,7,12,4,17};
#define NEL 20

int main()
{
int i,nel=NEL;

cout << "Avant tri:" << endl;
for(i=1;i<=NEL;i++)
  cout << tabint[i] << " ";

for(i=nel/2;i>0;i--)
  arranger(i,nel);

// [0] sert de var d'échange
tabint[0]=tabint[nel];
tabint[nel]=tabint[1];
tabint[1]=tabint[0];
nel--;
i=1;

do
  {
  arranger(i,nel);
  tabint[0]=tabint[nel];
  tabint[nel]=tabint[1];
  tabint[1]=tabint[0];
  nel--;
  }  while(i<=nel/2);

cout << endl << "Apres tri:" << endl;
for(i=1;i<=NEL;i++)
  cout << tabint[i] << " ";

return 0;
}

void arranger(int i,int nel)
{
int j=2*i;

while(j<=nel)
  {
  if(j+1<nel && tabint[j] < tabint[j+1])
    j++;
  if(tabint[i] < tabint[j])
    {
    tabint[0]=tabint[i];
    tabint[i]=tabint[j];
    tabint[j]=tabint[0];
    }
  i=j;
  j*=2;
  }
}

Conclusion :


Il trie des entiers.
Comme d'hab:
questions, commentaires, améliorations, ... laissez un message
Tout a fait compatible avec .NET (excepté les flux qui sont deprecated)

Niveau 3: pas simple de saisir l'idée
Télécharger le projet

Codes Sources

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (superpa)