Cette source corrige un problème lié au zéro, et prend acte des critiques reçues par la première version.
Source / Exemple :
/*
- PROJET : TriDicho AUTEUR : Alexandre Alcuyet DATE : 27/09/2008
- Trier un tableau par dichotomie.
- Le tri par dichotomie est un tri très efficace qui consiste
- à éliminer successivement la motié des possibilités restantes,
- jusqu'à parvenir au résultat.
- Ce code n'a qu'un intérêt pédagogique, au titre d'algorithme car
- l'API contient déjà de nombreuses solutions pour trier. Il
- n'est pas question ici de trier des Collections mais des entiers,
- mais libre à vous d'adapter le code.
- /
import java.io.IOException;
import java.lang.Integer;
public class Main {
public static void main(String args[]) throws IOException {
Integer[] tnb = {
Integer.valueOf(0), Integer.valueOf(54),
Integer.valueOf(2), Integer.valueOf(321326),
Integer.valueOf(1255), Integer.valueOf(10128),
Integer.valueOf(65), Integer.valueOf(4),
Integer.valueOf(101254), Integer.valueOf(4),
Integer.valueOf(10), Integer.valueOf(5),
Integer.valueOf(3), Integer.valueOf(1),
Integer.valueOf(8) };
affichetableau(tnb);
tnb = TriDicho.trier(tnb);
affichetableau(tnb);
System.exit(0);
}
public static void affichetableau(Object tab[])
throws IOException {
for ( int i=0; i<tab.length-1; i++)
System.out.format("%s - ", tab[i].toString());
System.out.format("%s%n",tab[tab.length-1].toString());
}
}
class TriDicho {
public static Integer[] trier(Integer tab1[])
throws IOException {
int debut = 0;
int fin = 0;
int pos = 0;
Integer[] tab2 = new Integer[tab1.length];
for ( int i=0; i<tab2.length; i++) {
pos = rechercheposition(tab1[i].intValue(),
tab2, debut, fin);
fin = i;
insertion(tab1[i].intValue(), tab2, pos);
};
return tab2;
}
private static void insertion( int val, Integer tab[], int pos)
throws IOException {
int zr;
for ( int i=tab.length-2; i>pos-1 ; i-- ) {
zr =
(tab[i] == null) ? 0 : tab[i].intValue() ;
if ( pos != i )
tab[i] = tab[i-1] ;
else
tab[i] = val ;
tab[i+1] = zr;
};
}
private static int round(double nb) throws IOException {
int monint = (int)nb;
double mondouble = (double)monint;
if ( mondouble != nb)
return (int)nb+1 ;
return (int)nb;
}
private static int rechercheposition(int val, Integer tab[],
int debut, int fin) throws IOException {
int milieu;
do {
milieu = round((double)((double)debut+(double)fin)/2);
/*
- si la valeur du tableau est null et que la fin (nombre
- le plus grand connu) est 0 retourne 0.
- Dans le cas du premier nombre inscrit au tableau
- /
//System.out.println("valeur: "+tab[0].intValue());
if ( (tab[milieu] == null) && (fin==0) )
return 0 ;
/*
- si la valeur est superieure et qu'il n'y a plus
- d'écart entre fin et debut retourne fin+1
- /
if ( (tab[milieu].intValue() <= val) && (debut == fin) )
return fin+1 ;
/*
- si la valeur est inferieure et qu'il n'y a plus d'ecart
- entre fin et debut retourne fin+1
- /
if ( (tab[milieu].intValue() > val) && (debut == fin) )
return fin ;
/*
- quand la valeur du tableau coordonee milieu est
- superieure a la valeur a entrer
- /
if ( tab[milieu].intValue() > val ) {
/*
- si il ne reste que deux cases,
- alors la deuxieme est inutile
- /
if (fin-debut == 1)
fin = fin-1 ;
// sinon fin est initialise avec milieu
else
fin = milieu;
}
/*
- si la valeur du tableau a la coordonee de milieu
- est inferieure ou egale a la valeur a entrer,
- alors on oublie tout ce qui se trouve avant
- /
if ( tab[milieu].intValue() <= val )
debut = milieu ;
}
while ( milieu != -1 );
return 0;
}
}
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.