|
TP6 Exercice 3.3
| #include "pile.h" #include <stdio.h> #include <stdlib.h> #define n 50 /* Taille du tableau */ #define seuil 9 /* seuil=0 pour un classement du tableau sans passer par le tri standard pour les petits intervalles */ #define SUP(a,b)(a>b)?0:1 /* Tri rapide par iteration, de Timan Fait le 15/04/01 http://www.timan.fr.st ou http://www.Software-DS.com */ /* Quelques commentaires Utilite des piles: on va s'en servir pour memoriser l'intervalle d'etude cad la borne inferieure et la borne superieure. Quelle doit etre la taille de la pile ? Pour le programme que j'ai ecrit, la taille de la pile doit etre de: (n-seuil)*2 Attention: Si le programme de votre prof est different, il est possible que la taille de la pile soit inferieure. Pour ameliorer la taille de votre pile il vous faut ameliorer la recherche de votre pivot. Plus votre pivot sera proche de la mediane et plus votre pile pourra avoir une taille petite et donc optimise. il est interessant de remarquer qu'il n'y a aucun moyen efficace de trouver la mediane d'un tableau qui n'est pas trie. */ typedef Element *pTab; void trirapide(pTab t,int min,int max); int partition(pTab t,int min,int max); void main(void){ int i; Element elt; pTab t; t=(Element*) calloc (n,sizeof(Element)); printf("\n Tri rapide semi-récursif (Quick Short)\n\n"); for(i=0;i<n;i++){ /* Saisie du vecteur */ printf("t[%d]= \n",i); scanf("%d",&elt); t[i]=elt; } printf("\nVotre tableau:\n"); for(i=0;i<n;i++){ /* Affichage */ printf("%d,",t[i]); } trirapide(t,0,n-1); /* Tri */ printf("\n\nVotre tableau trier:\n"); for(i=0;i<n;i++){ /* Affichage */ printf("%d,",t[i]); } printf("\n\nhttp://www.timan.fr.st\n"); /* ©2001 All Rights Reserved to www.Software-DS.com */ } /* ************************** trirapide ************************** */ void trirapide(pTab t,int min,int max){ int pivot; ptr_Pile pPile; p_creer (&pPile,(n-seuil)/2); /* Je suppose que n>seuil :-) */ pivot=partition(t,min,max); if (pivot>=0) { empiler(pPile,min); empiler(pPile,pivot-1); empiler(pPile,pivot+1); empiler(pPile,max); while(p_est_vide(pPile)==0) { depiler(pPile,&max); depiler(pPile,&min); pivot=partition(t,min,max); if (pivot>=0) { empiler(pPile,min); empiler(pPile,pivot-1); empiler(pPile,pivot+1); empiler(pPile,max); } } } p_raz(pPile); } /* ************************** partition ************************** */ int partition(pTab t,int min,int max){ int i,j,k; Element z,p; if ((max-min)>seuil) { i=min; j=max; k=(i+j)/2; p=t[k]; /* On deplace le pivot a la fin. */ t[k]=t[j]; t[j]=p; j--; do { /* On classe les elements par rapport au pivot */ while(t[i]<p) { i++; } while(t[j]>p) { j--; } if (i<j) { z=t[i]; t[i]=t[j]; t[j]=z; } } while(i<j); z=t[i]; /* On remet le pivot a sa place (au 'milieu') */ t[i]=t[max]; t[max]=z; } else { /* tri classique de l'intervalle */ int u,j; for(u=min;u<=max;u++){ int mini=t[u]; for(j=u+1;j<=max;j++){ if (t[j]<mini) { mini=t[j]; t[j]=t[u]; t[u]=mini; } } } i=-1; /* Pour dire qu'il n'y a pas de pivot et intervalle trier */ } return i; /* On renvoie la position du pivot */ } /* ©2002 All Rights Reserved to Didier STRAUS http://www.Software-DS.com */ } |
Haut de la page -
Page précédente -
Page générée en 0.02782 sec.
|
||||||
