Exemple de programmation

en langage C

de QuickSort

(Hoare, 1962)

[en Pascal]

#include <stdio.h>

 

/* il y a deux sous ensemble note A et B sur le tableau de départ noté X

l'élément du centre est celui qui va induire la construction de A et B

cet élément est d'abord placer dans la premiere case du sous-ensemble A ligne i

les autres éléments sont placer en A si ils sont plus petit que A[1]

*/

 

void triRapide(int v[], int gauche, int droit);

void triRapide(int v[], int gauche, int droit)

{

int i, dernier;

void echanger(int v[], int i, int j);

 

if(gauche>=droit)

return;

echanger(v,gauche,(gauche+droit)/2); /* i */

/*place l'élément du centre en v[0] */

dernier=gauche;

for(i=gauche+1;i<=droit;i++)

if (v[i]<v[gauche])

echanger(v,++dernier,i);

echanger(v,gauche,dernier);

/* remet en place l'élément de partage */

triRapide(v,gauche,dernier-1);

triRapide(v,dernier+1,droit);

}

 

void echanger(int v[], int i, int j);

void echanger(int v[], int i, int j)

{

/* echange v[i] et v[j] */

int temp;

temp=v[i];

v[i]=v[j];

v[j]=temp;

}

 

void display (int v[], int i, int j);

void display (int v[], int i, int j)

{

int k;

printf("\nDisplay\n");

for(k=i;k<=j;k++)

printf(" %d ",v[k]);

printf("\n");

}

 

void storage (int v[], int i, int j);

void storage (int v[], int i, int j)

{

int k;

printf("\nStorage\n");

for(k=i;k<=j;k++)

scanf("%d",&v[k]);

}

 

void main()

{

int vect[10];

storage(vect,0,9);

display(vect,0,9);

triRapide(vect,0,9);

display(vect,0,9);

}

/* ok c'est terminé */

Exemple

Valeur	3	8	5	4	7	6	2	9
Indice	1	2	3	4	5	6	7	8

echanger(v,gauche,(gauche+droit)/2);

Valeur	4	8	5	3	7	6	2	9
Indice	1	2	3	4	5	6	7	8

i=2;dernier=1

for(i=gauche+1;i<=droit;i++)

if (v[i]<v[gauche])

echanger(v,++dernier,i);

 

de i=2 à 3 inclu rien

Pour i=4

Valeur	4	3	5	8	7	6	2	9
Indice	1	2	3	4	5	6	7	8

 

 

de i=5 à 6 inclu rien

Pour i=7

Valeur	4	3	2	8	7	6	5	9
Indice	1	2	3	4	5	6	7	8

 

 

 

echanger(v,gauche,dernier);

Valeur	2	3	4	8	7	6	5	9
Indice	1	2	3	4	5	6	7	8

 

Conclusion:

On voit alors que entre les indices 1 et 3 inclu sont tous les éléments <= à 4, entre 4 et 8 inclu tous les éléments > à 4.