begin process at 2010 02 10 17:32:29
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Tutoriaux

 > QUICKSORT, ALGORITHME DE TRI EN O(N LOG N)

QUICKSORT, ALGORITHME DE TRI EN O(N LOG N)


 Information sur la source

Note :
7 / 10 - par 1 personne
7,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Catégorie :Tutoriaux Niveau :Initié Date de création :19/10/2003 Vu / téléchargé :5 309 / 165
Auteur : gvhecke

Ecrire un message privé
Site perso
Commentaire sur cette source (3)
Ajouter un commentaire et/ou une note

 Description

Il s'agit d'une implentation de l'algorithme de tri QuickSort... Algorithme récursif dont la complexité est en O (n log n) ... bien plus optimal que les méthodes traditionelle en O (n^2)...

Ce code est fort util pour trier un tableau de manière rapide. Le tableau peut être de type entier, double, long double ou tout autre type défini par un template et pour lequel il existe les oprérateurs < et >

Source

  • // Quicksort: version optimisée
  • // On place le maximum en variables globales (stack minimal)
  • // On optimise l'estimation de la médiane
  • // On trie les petits paquets par insertion linéaire
  • template <class X>
  • void swap(X& a, X& b)
  • {
  • X temp=a;
  • a=b;
  • b=temp;
  • }
  • template <class T>
  • void Tri (T a[], unsigned n) {
  • QSort<T> X(a, n);
  • }
  • template <class T>
  • class QSort {
  • static const unsigned LIM;
  • T x;
  • unsigned i, j;
  • void QS (T[], unsigned);
  • void TL (T[], unsigned);
  • public:
  • QSort (T a[], unsigned n) {QS(a, n); TL(a, n);}
  • };
  • template <class T>
  • const unsigned QSort<T>::LIM = 8; // >= 3
  • template <class T>
  • void QSort<T>::QS (T a[], unsigned n) {
  • while (n > LIM) {
  • i = 0; j = n-1;
  • if (a[0] < a[j/2]) swap(a[0], a[j/2]);
  • if (a[j/2] < a[j]) swap(a[j/2], a[j]);
  • if (a[0] < a[j/2]) swap(a[0], a[j/2]);
  • x = a[j/2];
  • for (;;) {
  • for (; a[i] > x; ++i);
  • for (; a[j] < x; --j);
  • if (i >= j) break;
  • swap(a[i], a[j]);
  • ++i; --j;
  • }
  • if (i < n-1-j) {
  • a += j+1; n -= j+1;
  • QS(a-(j+1), i);
  • }
  • else {
  • n ^= i; i ^= n; n ^= i; // = swap(i,n)
  • QS(a+j+1, i-1-j);
  • }
  • }
  • }
  • template <class T>
  • void QSort<T>::TL (T a[], unsigned n) {
  • // Placer minimum en a[0]
  • x = a[0]; j = 0;
  • for (i = 1; i < LIM && i < n; ++i) // Limité à LIM
  • if (a[i] > x) {x = a[i]; j = i;}
  • a[j] = a[0]; a[0] = x;
  • // Tri par insertion linéaire
  • for (i = 2; i < n; ++i) {
  • x = a[i];
  • for (j = i-1; a[j] < x; --j) a[j+1] = a[j]; // Limité à LIM
  • a[j+1] = x;
  • }
  • } 
// Quicksort: version optimisée
//    On place le maximum en variables globales (stack minimal)
//    On optimise l'estimation de la médiane
//    On trie les petits paquets par insertion linéaire

template <class X>
void swap(X& a, X& b)
{
	X temp=a;
	a=b;
	b=temp;
}

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

template <class T>
class QSort {
	static const unsigned LIM;
	T x;
	unsigned i, j;
	void QS (T[], unsigned);
	void TL (T[], unsigned);
public:
	QSort (T a[], unsigned n) {QS(a, n); TL(a, n);}
};

template <class T>
const unsigned QSort<T>::LIM = 8; // >= 3

template <class T>
void QSort<T>::QS (T a[], unsigned n) {
	while (n > LIM) {
		i = 0; j = n-1;
		if (a[0] < a[j/2]) swap(a[0], a[j/2]);
		if (a[j/2] < a[j]) swap(a[j/2], a[j]);
		if (a[0] < a[j/2]) swap(a[0], a[j/2]);
		x = a[j/2];
		for (;;) {
			for (; a[i] > x; ++i);
			for (; a[j] < x; --j);
		if (i >= j) break;
			swap(a[i], a[j]);
			++i; --j;
		}
		if (i < n-1-j) {
			a += j+1; n -= j+1;
			QS(a-(j+1), i);
		}
		else {
			n ^= i; i ^= n; n ^= i; // = swap(i,n)
			QS(a+j+1, i-1-j);
		}
	}
}

template <class T>
void QSort<T>::TL (T a[], unsigned n) {
	// Placer minimum en a[0]
	x = a[0]; j = 0;
	for (i = 1; i < LIM && i < n; ++i) // Limité à LIM
		if (a[i] > x) {x = a[i]; j = i;}
	a[j] = a[0]; a[0] = x;
	// Tri par insertion linéaire
	for (i = 2; i < n; ++i) {
		x = a[i];
		for (j = i-1; a[j] < x; --j) a[j+1] = a[j]; // Limité à LIM
		a[j+1] = x;
	}
}

 Conclusion

pour l'utiliser faites appel à l'aglorithme en créeant une instance de la classe QSort.

Par exemple:

#include "QSort.h"

int maint(void)
{
    int tableau* = new int [taille];
    remplir_tableau_avec_des_valeurs( tableau , taille);
    QSort<int> QSort (tableau,taille);
}

 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip


 Sources du même auteur

Source avec Zip COMPILATEUR: FORMAT GRAPHIXML VERS FORMAT POSTSCRIPT ET PDF
Source avec Zip Source avec une capture COMPILATEUR EMBEDDED C
Source avec Zip Source avec une capture INTELLIGENCE ARTIFICIELLE: ALGO GÉNÉTIQUE, VOYAGEUR DE COMME...
Source avec Zip HEAPSORT ALGORITHME DE TRI EN O(N LOG N)
Source avec Zip DIJKSTRA INDIQUE LA DISTANCE LA PLUS COURTE ENTRE UN SOMMET ...
Toutes les sources de gvhecke

 Sources de la même categorie

AFFICHAGE D'UN TRIANGLE ISOCELE par nabche
Source avec Zip GESTION D'UNE BIBLOTHEQUE par leclerro19
[PSP]HELLO WORLD par Mario1095
Source avec Zip Source avec une capture UTILISER LA LIB DIRENT par Lemng
UN TABLEAU MULTIDIMENTIONNEL COMME PARAMETRE DE FONCTION EN ... par Mcjo
Toutes les sources de la catégorie Tutoriaux

Commentaires et avis

Commentaire de D1m3x le 02/11/2003 17:48:17

bon ça fait longtemps que je regarde des codes comme celui-la, et à chaque fois je ne peux pas tout comprendre  à cause d'un petite conner*** celle-ci:

template &lt;...&gt;

je ne sais pas à quoi servent les &lt;&gt; :'( serais tu me l'expliquer STP??? au moins j'apprendrai quelque chose de nvo :)

j'espère que tu pourras m'aider....

bye

Commentaire de gvhecke le 03/11/2003 21:56:50

Il arrive souvent de vouloir réutiliser un même algorithme pour manipuler des structures différentes. Par exemple, trier un vercteur d'entier (int), un vecteur de réels (double), de nombres à virgule flottante (float), de string de caractère (char* ou char[]).

Il serait bien bête de devoir réimplenter à chaque fois une nouvelle fonction alors que dans l'ensemble, le code reste identique. Il n'y a que le type des variables que l'on manipule qui diffère (une fois int, une autre fois double ou float...)

Afin de permettre ce genre de chose, le language c++, permet en plaçant la ligne template &lt;classe Type&gt; de généraliser l'usage d'une fonction ou d'une class.

Dans l'exemple ci-dessus, j'ai coder la fonction QuickSort dans une classe (généralisée par l'usage de la ligne template &lt;class T&gt;). Le vecteur peut alors être de type T. Pour que cela fonctionne il faut que les opérateur "&gt;" et "&lt;" ait été défini pour les objet de class T. s'il on veut pouvoir trier des vecteur de string par ordre alphabétique, il faut avoir défini les opérateur "&lt;" et "&gt;" pour les string.

définition d'une fonction généralisée:
==========================
template &lt;class Type&gt;
type_retour nom_Fonction (Type variable1, Type variable2, ...);

définition d'une classe généralisée:
=========================
template &lt;class Type&gt;
class MaClasse
{
  public:
      MaClasse(); //constructeur
      ~MaClasse(); //Destructeur
      Type& NomFonction(const Type& var); //expl de fonction membre
      ...
  private: //membre, champs de ma classe
     Type membre1; //variable de type Type
     Type* pointeurVersMembre2; //pointeur vers une var de type Type
     int AutreMembre;
     ...
};

template &lt;class Type&gt;
MaClasse&lt;Type&gt;::MaClasse() {...} //définition du constructeur

template &lt;class Type&gt;
Type& MaClasse&lt;Type&gt;::NomFonction(const Type& var)
{...} //exemple de fonction membre d'une classe


Déclaration d'une variable MaClasse de type int:
===================================
MaClasse&lt;int&gt; var;

Déclaration d'un meme objet pour le type float:
==================================
MaClasse&lt;float&gt; var;


Voilà.

J'espère que ca t'éclairera.

Geofrey

Commentaire de D1m3x le 04/11/2003 19:00:39

Je dirais même que ça m'a complètement éclairer, merci, vraiment!!! Je comprend enfin à quoi ça sert ^^ lol

bon ben je vais essayer de l'utiliser alors :p

Merci encore :)

 Ajouter un commentaire

Nos sponsors


Sondage...

Comparez les prix


HTC Hero
Entre 550€ et 550€

Visiter le guide achat

CalendriCode

Février 2010
LMMJVSD
1234567
891011121314
15161718192021
22232425262728

Consulter la suite du CalendriCode
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 0,624 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)