Quicksort - non recursif

Commenter

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

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