Quicksort - non recursif

Soyez le premier à donner votre avis sur cette source.

Snippet vu 11 649 fois - Téléchargée 31 fois

Contenu du snippet

Comme promis , voici une possibilité d'implémentation du Tri rapide sans récursivité. Le principe est simple et est représentatif des appels de fonctions dans le cas de la récursivité. En effet les appels des fonctions sont nuisibles généralement ( à mon avis ) à cause des sauvegardes sur la pile(arguments , adresse de retour , registres) et des réallocations mémoires. Une simple boucle et un " push - pop" des arguments représenté par une file ( ici un tableau avec un _ index) comble parfaitement le mecanisme de la recursivite, qui d'ailleurs ne sert qu'à alleger un code plutôt qu'àa l'optimiser.
Ceci etant ma première source , j'espère que vous serez indulgents.
Merci pour vos commentaires, et vos critiques

Source / Exemple :


#include <stdlib.h>
#define RHASH	10000000

void quicksort(int* const tablo, const int first , const int last)
 {
	//first = premier index du tableau
	//last   = dernier index du tableau
	int debut;
	int fin;
        int begin;
	int end;
	int pivot;
	int temp;

	int index=0;
	int size=0;
	int capacite = RHASH+2;

	//allocation de la file
	int* queue = NULL;
	int* cursor;
	int* indexc;
	
	queue = (int*)malloc(capacite*sizeof(int));
		
	if(queue == NULL)
		return;

	cursor = queue;
	indexc = queue;

  • (cursor++) = first; //sauvegarde du debut du tablo a trier
  • (cursor++) = last; //sauvegarde de la fin du tablo a trier
index = 0; size = 2; do { debut = *(indexc++); //recuperation de l'indice de debut fin = *(indexc++); //recuperation de l'indice de fin index+=2; if(debut < fin) { begin = debut; end = fin; pivot = tablo[fin];//on prend le dernier element comme valeur pivot do { //progresser jusqu'a un element superieur ou egal au pivot while ( (begin < fin) && (tablo[begin]<=pivot) ) begin++; //progresser jusqu'a un element inferieur ou egal au pivot while ( (end > begin) && (tablo[end]>=pivot) ) end--; //echanger les 2 elements qui sont dans le mauvais ordre //comparativement au pivot if (begin < end) { temp = tablo[end]; tablo[end] = tablo[begin]; tablo[begin] = temp; } }while(begin < end);//continuer a parcourir le tablo //mettre le pivot a sa place dans le tableau trie temp = tablo[fin]; tablo[fin] = tablo[begin]; tablo[begin] = temp; //sauvegarder les indexes des prochains tris a faire // dans les sous-tableaux prochains // a savoir : a gauche du pivot , puis a droite du pivot //sauvegarde du debut du sous-tableau a trier => a gauche du pivot
  • (cursor++) = debut;
//sauvegarde de la fin du sous-tableau a trier => a gauche du pivot
  • (cursor++) = begin-1;
//sauvegarde du debut du sous-tableau a trier => a droite du pivot
  • (cursor++) = begin+1;
//sauvegarde de la fin du sous-tableau a trier => a droite du pivot
  • (cursor++) = fin;
size+=4; if(size==capacite) { capacite += RHASH; cout<<"rehash"<<endl; queue = (int*)realloc(queue,capacite*sizeof(int)); cursor = queue; indexc = &cursor[index]; if(queue == NULL) return; } } } while(index<size); cursor = NULL; indexc = NULL; free(queue); }

Conclusion :


Enjoy it.... :D

A voir également

Ajouter un commentaire Commentaires
cs_Maroi
Messages postés
10
Date d'inscription
mercredi 30 décembre 2009
Statut
Membre
Dernière intervention
1 avril 2012

30 avril 2010 à 12:51
Merci bcp pour votre réponse, mais en fait je cherche un programme en C??
shenron666
Messages postés
229
Date d'inscription
dimanche 14 septembre 2003
Statut
Membre
Dernière intervention
20 août 2014

29 avril 2010 à 20:53
je te conseille de passer par la stl en utilisant par exemple un std::vector<double> et la méthode de tri std::sort
cs_Maroi
Messages postés
10
Date d'inscription
mercredi 30 décembre 2009
Statut
Membre
Dernière intervention
1 avril 2012

29 avril 2010 à 20:41
Salut,
Est ce que vous pouvez donner un exemple de quicksort non récursif pr les réels?
Merci bcp
shenron666
Messages postés
229
Date d'inscription
dimanche 14 septembre 2003
Statut
Membre
Dernière intervention
20 août 2014

14 mars 2006 à 12:01
Salut les gens, bon j'ai pris le temps ce matin de venir aux nouvelles et j'ai vu le post de Noxk
J'avais un big problème avec mon algo lorsqu'on triait 2 fois de suite un tableau : dépassement de pile
du coup je n'avais pas fait attention qu'en plus je n'avais pas mis la bonne version en ligne qui, en effet ne trait pas
j'ai pas l'air con -__-

bref, j'ai corrigé à partir d'un algo repris sur un site très bien fait :
http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

le tri de 10 millions de valeurs me donne les temps suivants (en ms) :
nickydaquick (RHASH = 10000) : 797
Brunews : 2360
qsort CRT : 2906
mon tri récursif : 4750
avec la std : 1187 (std::sort d'un vector)
avec la std : 2671 (std::sort_heap d'un vector)

j'ai aussi essayé de trier plusieurs fois de suite un tableau, vu que je rencontrais des problèmes avec mon algo
bizarrement le tri de nickydaquick prend de plus en plus de temps, je n'ai pas regardé pourquoi
Le tri de Brunews s'en sort très bien

au final je trouve l'algo de brunews plutot performant, dommage que je sois si buté sur les goto ^_^
je me répète en disant que je trouve la méthode de nickydaquick intéressante
dès que j'aurai plus de temps je regarderai si je peux faire la même chose pour un CArray
Noxk
Messages postés
10
Date d'inscription
dimanche 26 février 2006
Statut
Membre
Dernière intervention
27 mars 2007

14 mars 2006 à 09:28
Salut Nicky,

J'ai effectué les test comme tu l'indiquais et les temps donnés pour le tri sont reellement meilleur mais y a un bogue, le tri est partiellement effectué. Ceci provient du fait que tu as oublié de remettre cursor a sa position final quand tu realloues la memoire.

Ca se corrige en remplacant les "*(cursor++)" par des "*(cursor + i++)" et ensuite dans la condition "if" mettre "*(cursor + i);"


Mais meme avec ca on remarque un probleme, tu rentres trop souvent dans la condition "if" de realloc et ca bouffe un temps enorme.Ce que je te propose, vu que tu utilise dans ton algo une pile, que tu ne depiles jamais, c'est justement s'en servir comme d'une pile qu'on depile et plus besoin de realloué la memoire, le seul probleme reside dans le fait de definir une taille de la pile suffisante.

Je me permets de mettre le code corrigé a ma manière et qui ressemble un peu a celui que j'ai écrit sur l'aspect pile/depile.

#define RHASH 100000

void quicksort(int* const tablo, const int first , const int last)
{
//first = premier index du tableau
//last = dernier index du tableau
int debut;
int fin;
int begin;
int end;
int pivot;
int temp;
int i=0;

int index=0;
int size=0;
int capacite = RHASH+2;

//allocation de la file
int* queue = NULL;
int* cursor;
int* indexc;

queue = (int*)malloc(capacite*sizeof(int));

if(queue == NULL)
return;

cursor = queue;
indexc = queue;

*(cursor + i++) = first; //sauvegarde du debut du tablo a trier
*(cursor + i++) = last; //sauvegarde de la fin du tablo a trier
index = 0;
size = 2;

do
{
//debut = *(indexc++); //recuperation de l'indice de debut
//fin = *(indexc++); //recuperation de l'indice de fin
fin = *(cursor + --i); //recuperation de l'indice de fin
debut = *(cursor + --i); //recuperation de l'indice de debut


index+=2;

if(debut < fin)
{
begin = debut;
end = fin;
pivot = tablo[fin];//on prend le dernier element comme valeur pivot

do
{
//progresser jusqu'a un element superieur ou egal au pivot
while ( (begin < fin) && (tablo[begin]<=pivot) )
begin++;
//progresser jusqu'a un element inferieur ou egal au pivot
while ( (end > begin) && (tablo[end]>=pivot) )
end--;

//echanger les 2 elements qui sont dans le mauvais ordre
//comparativement au pivot
if (begin < end)
{
temp = tablo[end];
tablo[end] = tablo[begin];
tablo[begin] = temp;
}

}while(begin < end);//continuer a parcourir le tablo

//mettre le pivot a sa place dans le tableau trie
temp = tablo[fin];
tablo[fin] = tablo[begin];
tablo[begin] = temp;


//sauvegarder les indexes des prochains tris a faire
// dans les sous-tableaux prochains
// a savoir : a gauche du pivot , puis a droite du pivot

//sauvegarde du debut du sous-tableau a trier => a gauche du pivot
*(cursor + i++) = debut;
//sauvegarde de la fin du sous-tableau a trier => a gauche du pivot
*(cursor + i++) = begin-1;

//sauvegarde du debut du sous-tableau a trier => a droite du pivot
*(cursor + i++) = begin+1;
//sauvegarde de la fin du sous-tableau a trier => a droite du pivot
*(cursor + i++) = fin;
size+=4;

// if(size==capacite)
// {
// capacite += RHASH;
// cout << "rehash" << endl;
// queue = (int*)realloc(queue,capacite*sizeof(int));
// cursor = queue;
// indexc = &cursor[index];
//*(cursor + i);
// if(queue == NULL)
// return;
// }
}
}
while(index<size);
cursor = NULL;
indexc = NULL;
free(queue);
}

Reste plus qu'a trouver un matheux pour trouver la formule de la taille de la pile en rapport avec celle du tableau :)

Sinon au niveau des score maintenant tu es meilleur que le mien mais reste tres legerement en dessous de ceux de BruNew.
Afficher les 37 commentaires

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.