Accueil     Soft. MacOSX     Soft. MacOS/PC     PHP     ROMS GBA     TP d'info     TI-92     DBZ-GT     Martingales     Galeries     Liens     @  

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.01084 sec.
Recherche personnalisée
 

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