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 générée en 0.00430 sec.
 

1847337 visiteurs.   ©2001-2024 All Rights Reserved to Software-DS.com
Made with a mac  
Confidentialité