Tri d'un tableau

Soyez le premier à donner votre avis sur cette source.

Snippet vu 6 890 fois - Téléchargée 34 fois

Contenu du snippet

voila un simple et court algorithme de tri

Source / Exemple :


#include <stdio.h>
#include <conio.h>
//=======================================================================
//  AFFICHAGE D'UN  TABLEAU :
//=======================================================================
void Affiche(int *tab,int nbElem,int espacement)
{
printf("{ %*d",espacement,*tab);
while(--nbElem)
  {
  printf(",%*d",espacement,*(++tab));
  }
printf(" }\n");
}
//=======================================================================
//  ECHANGE DEUX VARIABLES
//=======================================================================
void Echange(int *a,int *b)
{
int tmp;
tmp = *a;

  • a = *b;
  • b = tmp;
} //======================================================================= // TRI D'UN TABLEAU : //======================================================================= void Tri(int *tab,int nbElem) { int i; for(i=nbElem;i>1;i--) { int *p,*pMax,max,j; // on initialise <p> et <max> et <pMax> en meme temps ! max = *(pMax = p = tab); // le j=0 a deja ete traiter au decu ! for(j=1;j<i;j++) { if(*(++p) > max) { max = *(pMax = p); } } Echange(p,pMax); Affiche(tab,nbElem,3); } } //======================================================================= // MAIN //======================================================================= int main(int argc,char **argv) { int tab[] = {9,-1,8,-2,7,-3,6,-4,5,-4,4,-6,3,-7,2,-8,1,-9,0}; Tri(tab,sizeof(tab)/sizeof(tab[0])); getch(); return 0; }

Conclusion :


L'algorithme est tres simple :
On a <n> nombres a trie.
Par exemple 5 nombres {5,6,3,-10,2}

On calcul le plus grand nombre parmis ces 5
Puis on le permute avec le 5eme nombre.
Dans l'exemple on permute le 6 avec le 2.
Ainsi on a {5,2,3,-10,6}

On recommence non-plus avec 5, mais 4:
On calcul le plus grand nombre parmis les 4 premier
Puis on le permute avec le 4eme nombre.
Dans l'exemple on permute le 5 avec le -10.
Ainsi on a {-10,2,3,5,6}

Ainsi de suite, on obtient peu a peu ces tableaux:
{ 5, 2, 3,-10, 6 }
{ -10, 2, 3, 5, 6 }
{ -10, 2, 3, 5, 6 }
{ -10, 2, 3, 5, 6 }

Le dernier est biensur (et forcement) trie !
Le nombre d'etape est de n-1
Cet algorithme est en n².

Ce programme montre les differentes etapes de ce mode de tri
que l'on peut appeller tri par permutation.

Dans l'exemple d'au dessus on peut remarquer qu'il suffit
de faire 1 etapes pour que le tableau soit tri.
Mais l'avantage c'est que dans des cas extreme, on est
comme meme sur a 100% que le tri sera fait.
Les cas extremes sont quand la moitie des nombres
sont deja ranges dans le sens contraire :
Exemple {9,-1,8,-2,7,-3,6,-4,5,-4,4,-6,3,-7,2,-8,1,-9,0}
Le programme donne les resultats suivants :
{ 0, -1, 8, -2, 7, -3, 6, -4, 5, -4, 4, -6, 3, -7, 2, -8, 1, -9, 9 }
{ 0, -1, -9, -2, 7, -3, 6, -4, 5, -4, 4, -6, 3, -7, 2, -8, 1, 8, 9 }
{ 0, -1, -9, -2, 1, -3, 6, -4, 5, -4, 4, -6, 3, -7, 2, -8, 7, 8, 9 }
{ 0, -1, -9, -2, 1, -3, -8, -4, 5, -4, 4, -6, 3, -7, 2, 6, 7, 8, 9 }
{ 0, -1, -9, -2, 1, -3, -8, -4, 2, -4, 4, -6, 3, -7, 5, 6, 7, 8, 9 }
{ 0, -1, -9, -2, 1, -3, -8, -4, 2, -4, -7, -6, 3, 4, 5, 6, 7, 8, 9 }
{ 0, -1, -9, -2, 1, -3, -8, -4, 2, -4, -7, -6, 3, 4, 5, 6, 7, 8, 9 }
{ 0, -1, -9, -2, 1, -3, -8, -4, -6, -4, -7, 2, 3, 4, 5, 6, 7, 8, 9 }
{ 0, -1, -9, -2, -7, -3, -8, -4, -6, -4, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
{ -4, -1, -9, -2, -7, -3, -8, -4, -6, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
{ -4, -6, -9, -2, -7, -3, -8, -4, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
{ -4, -6, -9, -4, -7, -3, -8, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
{ -4, -6, -9, -4, -7, -8, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
{ -8, -6, -9, -4, -7, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
{ -8, -6, -9, -7, -4, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
{ -8, -7, -9, -6, -4, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
{ -8, -9, -7, -6, -4, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
{ -9, -8, -7, -6, -4, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Ici c'est seulement a la derniere etape que le tri est completement
effectue.

A voir également

Ajouter un commentaire

Commentaires

cs_NiFF
Messages postés
92
Date d'inscription
dimanche 2 juin 2002
Statut
Membre
Dernière intervention
24 juin 2004
-
Bien, mais quelques remarques à faire tout de même :
La présentation de l'algorithme à la fin est très agréable (et très rare).
Idem pour les jeux de test et la complexité.
Cet algo est trop lent sur des tableaux très grands (mieux vaut utiliser le quicksort, déjà existant en C : pour résumer, il coupe le tableau en 2 et trie les deux moitiés du tableau par un appel récursif).
spidermario
Messages postés
130
Date d'inscription
mercredi 26 octobre 2005
Statut
Membre
Dernière intervention
14 mars 2009
-
Pour la fonction d'échange, on peut éviter la variable temporaire avec :

a^=b;
b^=a;
a^=b;

Qui marche aussi bien.
spidermario
Messages postés
130
Date d'inscription
mercredi 26 octobre 2005
Statut
Membre
Dernière intervention
14 mars 2009
-
Et au fait, ceci n'est pas une source .Net...
BruNews
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
16 -
J'ai enlevé le flag .NET, surement une erreur pendant la dernière migration de nos bases, rien de bien important.

Impossible d'éviter le stockage temporaire partant de 2 adresses mémoire, ce n'est pas parce que tu ne la vois pas qu'elle n'y est pas, le compilo le fera pour toi. Un CPU n'accepte pas 2 opérandes mémoire sur une instruction, c'est ainsi et il n'y a rien à y faire. Le tout n'est pas de savoir si ça "marche aussi bien" mais si c'est plus performant, pour cela il faut regarder le listing asm produit et je redoute fort que ta série de XOR soit bien moins bonne.

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.