TRI TABLEAU D'INTEGER PAR DICHOTOMIE, MAJ

/*
 * 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;
	}
}

Télécharger le zip