Heapsort algorithme de tri en o(n log n)

Télécharger le projet
Commenter

Description

Algorithme du Heap Sort...

Il s'agit de voir les vecteur à trier comme des arbres binaires...

Et de le trier en arrangeant l'arbre pour en faire un Heap. Ensuite en partant de la dernière feuille swapper vecteur[n] avec la racine puis Arranger à nouveau l'arbre pour en faire un heap... et remonter l'arbre en s'arrangeant pour qu'après chaque swap on ait ensuite un heap...

Source / Exemple : 


// HeapSort: version optimisée

template <class T>
class HpSort {
   T* a;
   T x;
   void HS (unsigned);
   void Arrange (unsigned, unsigned);
public:
   HpSort (T _a[], unsigned n): a(_a) {if (n) HS(n);}
};

template <class T>
void Tri (T a[], unsigned n) {
   HpSort<T> X(a, n);
}

template <class T>
void HpSort<T>::Arrange (unsigned i, unsigned n) {
   unsigned j;
// x = a[i];
   while ((j = 2*i+1) < n) {
      if (j+1 < n && a[j] < a[j+1]) ++j;
      if (x >= a[j]) break;
      a[i] = a[j]; i = j;
   }
   a[i] = x;
}

template <class T>
void HpSort<T>::HS (unsigned n) { // n>0 !
   for (unsigned i = n/2; i; --i) {x = a[i-1]; Arrange(i-1, n);}
   while (--n) {
      x = a[n]; a[n] = a[0]; a[0] = x;
      Arrange(0, n);
   }
}

Conclusion :


//pour faire fonctionner l'algo:
#include "heapSort.h"

... //votre code

//Pour un objet T tel que les opérateurs >=, < sont défini
T* vecteurATrier = new T [tailleVecteur];
Tri(vecteurATrier,tailleVecteur);

//Tri() construit un objet HpSort avec le bon template <class T>
//et lance l'algo.

//La variable de travail x est un membre caché de la
//classe HpSort et est détruite en même temps que l'objet HpSort.

//En implantant l'algo dans une classe on a pas besoin d'une variable globale
//de travail... Tout est transparant et on gagne en mémoire.
Télécharger le projet

Codes Sources

A voir également

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 (gvhecke)