TP6 Exercice 3
| /* TP6 30/11/02 http://www.Software-DS.com */ #include <stdio.h> #include <stdlib.h> #define n 15 /* Taille du tableau */ #define seuil 1 /* 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 recurence de Timan Fait le 14/04/01 http://www.Software-DS.com */ typedef int Element; typedef Element *pTab; void quicksort(pTab t,int min,int max); int partition(pTab t,int min,int max); int main(void){ int i; Element elt; pTab t; t=(Element*) calloc (n,sizeof(Element)); printf("\n Tri rapide 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]); } quicksort(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.Software-DS.com\n"); return 0; /* ©2001-2002 All Rights Reserved to http://www.Software-DS.com */ } /* ************************** quicksort ************************** */ void quicksort(pTab t,int min,int max){ int pivot; if ((min<max) && ((max-min)>seuil)) { pivot=partition(t,min,max); quicksort(t,min,pivot-1); quicksort(t,pivot+1,max); } else if ((max-min)<=seuil) { /* classe les elements entre min et max par un tri classique */ int i,j; for(i=min;i<=max;i++){ int mini=t[i]; for(j=i+1;j<=max;j++){ if (t[j]<mini) { mini=t[j]; t[j]=t[i]; t[i]=mini; } } } } } /* ************************** partition ************************** */ int partition(pTab t,int min,int max){ int i,j,k; Element z,p; 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 elemnts 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; 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 générée en 0.01853 sec.
|
||||||
