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 précédente - Page générée en 0.01928 sec.

Recherche personnalisée
1843945 visiteurs. ©2001-2023 All Rights Reserved to Software-DS.com		Confidentialité