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
//sauvegarde de la fin du sous-tableau a trier => a gauche du pivot
//sauvegarde du debut du sous-tableau a trier => a droite du pivot
//sauvegarde de la fin du sous-tableau a trier => a droite du pivot
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
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.