Quicksort, algorithme de tri en o(n log n)

Télécharger le projet
Commenter

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 / Exemple : 


// 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);
}
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)