Problème en C, aider moi SVP!! Fermé

Question

Bonjour, est-ce que je pourrais savoir comment faire pour trier dans un tableau ?Est-ce-que je pourrais avoir auusi les solutions du tri par recherche des minimas, du tri à bulle et de la recherche dichotomique? Aider  moi SVP, j'en ai vraiment besoin pour mes études !!!

Marden · Answer

Voici, sorti de mes cartons et mes souvenirs, et déjà posté sur le forum ? de CCM, 3 types de tri, appliqué à des nombres flottants, et de quoi les tester. Sans garantie sur leur total validité. Le tri par fusion de monotonies de ma composition serait du même ordre de rapidité que le "Quick Sort". Bon courage.

#include <stdio.h>
#include <malloc.h>
#include <ctype.h>

main(argc,argv)
int argc ;
char *argv[] ;
{
double drand48() ;
float *array ;
int n, algo, nData, nLoop, i ;

if ( argc >= 3 ) {
nData = sscanf(argv[1],"%d",&n) ;
/* allocation et remplissage */
array = (float *) ( calloc(n,sizeof(float))) ;
for ( i=0 ; i<n ; i++ ) {
array[i] = drand48() * n ;
}
system("date") ;
algo = argv[2][0] ;
if ( argc > 3 ) {
nData = sscanf(argv[3],"%d",&nLoop) ;
} else {
nLoop = 1 ;
}
while ( nLoop ) {
switch ( algo ) {
case 'b' :
printf (" Tri Bulle\n") ; sortBulle(array,n) ;
break ;
case 'm' :
printf (" Tri Merge\n") ; sortMergeDic(array,n) ;
break ;
case 'q' :
printf (" Tri Quick\n") ; sortQuick(array,n) ;
break ;
default :
printf (" Usage Sort <nb_val> { b | m | q } [n_fois]\n") ;
exit(1) ;
}
system("date") ;
nLoop-- ;
}
/* contrôle de monotonie */
printf (" ==============\n") ;
for ( i=1, nData=0 ; i < n && nData < 10 ; i++ ) {
if ( array[i] < array[i-1] ) {
nData++ ;
printf(" error on array[%4d] = f\n",i,array[i] ) ;
}
}
free ( array ) ;
} else {
printf (" Usage Sort <nb_val> { b | m | q } [n_fois]\n") ;
exit(1) ;
}
}
/* ---------------------------------------------------------- */
sortBulle ( array, n ) {
float *array ;
int n ;
{
int i, j ;
float temp ;
for ( i=1 ; i < n ; i++ ) {
if ( array[i] < array[i-1] ) {
temp = array[i] ;
for ( j = i ; j > 0 && (array[j-1] > temp) ; j-- ) {
array[j] = array[j-1] ;
}
array[j] = temp ;
}
}
}
/* ---------------------------------------------------------- */
sortMergeDic ( array, n ) {
float *array ;
int n ;
{
int monoL, par ;
float *tmp, *rAdr1, *rAdr2, *rEnd2, * endRead, *wAdr ;
/* allouer un espace de même taille que la table à trier */
tmp = (float*) (calloc(n,sizeof(float))) ;

for ( monoL=1, par=1 ; monoL < n; monoL *= 2, par=1-par ) {
if ( par ) {
rAdr1 = array ;
wAdr = tmp ;
} else {
rAdr1 = tmp ;
wAdr = array ;
}
for ( endRead = rAdr1 + n ; rAdr1 < endRead ; rAdr1 = rEnd2 ) {
rEnd1 = rAdr1 + monoL ;
if ( rEnd1 < endRead ) {
rAdr2 = rEnd1 ;
rEnd2 = rAdr2 + monoL ;
if ( rEnd2 > endRead ) {
rEnd2 = endRead ;
}
} else {
rEnd1 = rAdr2 = rEnd2 = endRead ;
}
while ( rAdr1 < rEnd1 && rAdr2 < rEnd2 ) {
/* comparaison et transfert */
*wAdr++ = (*rAdr1 <= *rAdr2)? *rAdr1++ : *rAdr2++ ;
}
/* une monotonie est épuisée : vidage de l'autre */
if ( rAdr1 <= rEnd1 ) {
while ( rAdr2 < rEnd2 ) {
*wAdr++ = *rAdr2++ ;
}
} else {
while ( rAdr1 < rEnd1 ) {
*wAdr++ = *rAdr1++ ;
}
}
}
}
/* fin du tri : copie de "tmp" dans "array" si nécessaire */
if ( !par ) {
for ( rAdr1=tmp, endRead=rAdr1+n , wAdr=array ; rAdr1<endRead ; ) {
*wAdr++ = *rAdr1++ ;
}
}
free (tmp) ;
}
/* ---------------------------------------------------------- */
sortQuick ( array, n ) {
float *array ;
int n ;
{
sortQuickP(array,0,n-1) ;
}
sortQuickP( array,left, right )
float *array ;
int left,right ;
{
int k ;
if ( left < right ) {
k = place(array,left,right) ;
sortQuickP(array,left,k-1) ;
sortQuickP(array,k+1,right) ;
}
}
place(array,left,right)
float *array ;
int left,right ;
{
int gauche = left + 1 ;
int droite = right ;
int rang ;
float temp = array[left] ;
float trans ;
while ( left != right ) {
if ( array[gauche] <= temp ) {
gauche++ ;
} else if ( array[droite] > temp ) {
droite-- ;
} else {
trans = array[gauche] ;
array[gauche++] = array[droite] ;
array[droite] = trans ;
}
}
if ( array[gauche] <= temp ) {
rang = gauche ;
} else {
rang = gauche - 1 ;
}
array[left] = array[rang] ;
array[rang] = temp ;
return ( rang ) ;
}

l'autreGL · Answer

si tu recherche un tri qui a des performances un peu moins bonnes que le tri quicksort, mais avec une rendement constant, le tri en epi est utile.je n'ai pas l'algorithme la. tu devrais trouver ca sur le net.

si tu n'a que quelques nombres a trier, un tri bulle fait l'affaire.
Aussi minable qu'il soit, le tri bulle peut etre bien amelioré.

Problème en C, aider moi SVP!!

2 réponses

Discussions similaires