begin process at 2012 02 11 14:34:32
  Trouver un code source :
 
dans
 
Accueil > 

Code

 > 

Maths et Algorithmes

 > TRI TABLEAU D'INTEGER PAR DICHOTOMIE, MAJ

TRI TABLEAU D'INTEGER PAR DICHOTOMIE, MAJ


 Information sur la source

Note :
7 / 10 - par 1 personne
7,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Catégorie :Maths et Algorithmes Classé sous :dichotomique, dichotomie, algorithme, tri, ordonner Niveau :Débutant Date de création :27/09/2008 Vu / téléchargé :7 747 / 205

Auteur : xael2

Ecrire un message privé
Commentaire sur cette source (9)
Ajouter un commentaire et/ou une note

 Description

Cette source corrige un problème lié au zéro, et prend acte des critiques reçues par la première version.

Source

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


 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !
  • Main.classTélécharger ce fichier [Réservé aux membres club]1 092 octets
  • Main.javaTélécharger ce fichier [Réservé aux membres club]Voir ce fichier3 833 octets
  • TriDicho.classTélécharger ce fichier [Réservé aux membres club]1 254 octets

Télécharger le zip


 Sources du même auteur

Source avec Zip Source avec une capture NOMBRE ENTIER OU MONTANT EN LETTRES (FRANÇAIS & SUISSE)
Source avec Zip TRI TABLEAU D'ENTIER PAR DICHOTOMIE
Source avec Zip MASTER MIND MODE CONSOLE

 Sources de la même categorie

IMPLÉMENTATION DE L'ENSEMBLE C AVEC JAVA par Scupper
CALCUL D'EXPONENTIEL ( PRÉCISION MODIFIABLE) par Scupper
Source avec Zip TRANSFORMATION D'UNE EXPRESSION ARITHMETIQUE (INFIXÉ) EN POS... par billatosco
PROBLÈME DES N-REINES par jojolemariole
Source avec Zip ARRAYMATRIX -MATRICE MULTIDIMENSIONELLE ET GÉNÉRIQUE- , IMP... par labandus

 Sources en rapport avec celle ci

IMPLÉMENTATION DE L'ENSEMBLE C AVEC JAVA par Scupper
CALCUL D'EXPONENTIEL ( PRÉCISION MODIFIABLE) par Scupper
Source avec Zip Source avec une capture CITY 3, C'EST UN JEU DE VILLE par edouard333
Source avec Zip Source avec une capture ALGORITHME GENETIQUE PROBLEME DU VOYAGEUR DE COMMERCE par sarathai
Source avec Zip TRI TABLEAU D'ENTIER PAR DICHOTOMIE par xael2

Commentaires et avis

Commentaire de petifa le 28/09/2008 17:59:24

pas encore testé, mais je suppose que ca doit fonctionner.
Par contre trop de commentaires tue les commentaires...
bizarre la fonction rechercheposition est commentée mais pas le reste...

Commentaire de jaoued zahraoui le 29/09/2008 12:01:15

bien pour l'exploi technique, mais tout ca peut se resumer par une seule ligne :
Arrays.sort(tnb);

Commentaire de YvesDaoust le 29/09/2008 18:47:39


"Le tri par dichotomie est un tri très efficace"

D'accord pour dire que la recherche dichotomique dans une table triée est efficace. Elle prend un temps Log(N) pour N éléments.

Par contre le tri par recherche dichotomique et insertion est très inefficace à cause de la phase d'insertion, qui prend un temps N^2.

A proscrire !!! Les tris efficaces sont en N.Log(N).

Commentaire de xael2 le 30/09/2008 09:27:09

D'accord YvesDaoust, effectivement, il s'agit de la recherche par dichotomie sur données rangées en ce qui concerne l'efficacité. Pour le tri ça prend bien sur plus de temps.
Le cours abordant la dichotomie est arrivé après une semaine de cours consacrée aux algos de triage. C'est pour cette raison je pense qu'il nous a été demandé d'utiliser la dichotomie pour effectuer un tri.

Dès que j'ai le temps je posterai un algo de nombres-en-lettres pour me faire pardonner :)

Commentaire de robertjul le 20/01/2009 11:16:02 7/10

Merci beaucoup!

Commentaire de verdy_p le 25/02/2009 17:51:02

Effectivement la fonction du JRE Arrays.sort(tnb); est lpus efficace et est déjà très optimisée, elle n'a que très peu de cas défavorables. Pour l'insertion dans une collection triée, les méthodes natives du JRE sont également très efficaces et optimisées et savent aussi utiliser la dichotomie là où elle est pertinente (si la collection est représentée par un vecteur) ou une recherche récursive de type divide-and-conquer (pour la représentation de la collection triée en arbre, qu'il soit binaire ou plus, et semi-équilibré en AVL, ou totalement équilibré en B-arbre).
En revanche pour les collections triées dont les éléments ne sont pas tous en mémoire mais sont stockées de façon externe par un accès lent (fichier, service réseau distant...), le tri complet dans un vercteur est moins intéressant que les représentation sous forme d'arbre d'index (avec un cache local d'exlporation) complété d'une méthode d'équilibrage qui ne nécessite pas trop de réorganisations (pour les mises à jour) telle que les AVL, arbres bicolores, B-arbres, et arbres B+.
Dans ce cas ce qui est très intéressant à écrire c'est la fonction d'équilibrage (total ou partiel) de l'arbre, et la façon de modifier rapidement l'arbre (par insertion ou suppression d'éléments dans la collection) sans nécessairement maintenir un équilibrage total (et là des paramètres de tuning sont intéressants tels que le niveau minimum de remplissage des feuilles et noeuds dans un B-arbre), ainsi que les méthodes de parcours séquentiel de l'arbre (pour l'explorer dans l'ordre de tri).

De toute façon, dans chaque problème où intervient un tri, il faut se demander s'il est pertinent. Le tri est et a toujours été coûteux, on le relègue donc le plus souvent à la fin dans la présentation des résultats d'un problème: pratiquement toujours ce n'est pas le tri qui est nécessaire, mais simplement un test d'unicité (ou d'existence) dans une collection, et là le hachage fait des miracles, à condition que la fonction de hachage soit uniformément distribuée, ce que bien des programmes Java oublient de traduire dans la fonction de hachage de leurs objets, souvent simplement basée sur une simple évaluation de polynome ! Même pour hacher des entiers, un polynome est très insuffisant pour assurer cette uniformité de distribution (alors que l'inversion du poids des bits est une opération "simple" mais efficace pour avoir une assez bonne distribution du hachage dans nombre de problèmes relatifs à la recherche d'unicité).

Le hachage a cependant le défaut de ses avantages: il ne garantie aucun ordre pertient dans les éléments récupérés de la collection (mais le plus souvent on s'en fout royalement pour l'immense majorité des problèmes où on n'a à gérer que des ensembles d'éléments et non des collections triées).

Ainsi, trop de programmes font des requêtes SQL contenant un tri couteux (ORDER BY) alors qu'un groupement d'unicité suffit et est bien plus performant et suffisant pour le problème donné (GROUP BY). La même question se pose pour les index (dont il n'est souvent pas nécessaire qu'ils maintiennent triées les données d'une table à la quelle on accède uniquement par un identifiant ou une valeur unique, et non par une recherche par plage de valeurs), et sur la pertinence des recherches par plage (ce qui peut traduire un défaut de conception du modèle de données si ce type de recherche est trop systématique, car il est évident qu'il manque alors un attribut de type "classe énumérée")

Bref, faites du tri, mais avec modération !

Commentaire de jaoued zahraoui le 25/02/2009 18:15:13

ton commentaire est vraiment très intéressant verdy. on vois que tu t'es penché sur le sujet. ces mécanismes sont d'un niveau relativement bas, le développeur n'en a pas trop à s'en soucier en général. à part servir de cas d'école (cours d'algorithme, etc) ce genre de programme n'est pas très utilisé dans la vie professionnelle, on se concentre plus sur la partie métier. java à le grand avantage d'être réutilisable alors réutilisez ce qui existe déjà, d'autant plus qu'il est difficile de faire mieux en termes de performances (java ayant été longtemps critiqué sur ce point des efforts on été fait). par contre il est nécessaire de bien comprendre les fonctionnements de ces fonctions pour choisir celle qui est le mieux adaptée à chaque cas de figure.

Commentaire de robertjul le 28/02/2009 14:00:57

Merci beaucoup pour ces informations!

Commentaire de verdy_p le 01/03/2009 12:23:34

Puisqu'on parle de qualité de code et réutilisation, il serait important de notyer certains défauts dans le code ci-dessus:

(1) pourquoi tous ces "throws IOException" pour des méthodes qui ne font pas d'IO? C'est totalement inutile (et couteux) dans la classe TriDicho ci-dessus.

(2) voila une fonction d'arrondi très bizarre ! Non seulement elle ne fait pas un arrondi à l'entier le plus proche (en fait elle prend l'entier supérieur), mais en plus elle le fait avec un test complètement inutile et couteux, et avec deux conversion de type au passage.

Rappel:
  int round(double x) { return (int)(x + 0.5); }
suffit pour un arrondi à l'entier le plus proche, ou
  double round(double x) { return Math.floor(x + 0.5); }
si on veut une étendue numérique plus large au delà de +/-2^31.

(3) l'arrondi est en fait totalement inutile dans la dichotomie: il suffit de prendre la division entière par deux des intervalles, même si un des deux sous-intervalles est de longueur impaire et l'autre paire, lequel sera le plus long reste un choix arbitraire. Bref pour prendre un nombre entier moyen entre dex entiers, il suffit totalement de prendre:

  milieu = (debut + fin) / 2;

avec la division entière, au lieu du couteux et inutile:

  milieu = round((double)((double)debut+(double)fin)/2);

En effet, début et fin sont des index de tableaux, et ils sont nécessairement positifs ou nuls donc sur 31 bits, leur somme tient sans dépassement dans 32 bits (même si un signe négatif peut apparaître). Si on veut éviter le cas de la somme négative (qui peut apparaître seulement si les deux entiers positifs nécessitent 31 bits, donc tous deux supérieurs ou égal à 2,1 milliards), et éviter tout cas de débordement de capacité, on peut aussi écrire:

  milieu = (debut>>1)+(fin>>1)+(début&fin&1);

(pour comprendre cette formule, il faut voir que x>>1 divise un entier par 2, et qu'on s'occupe donc d'ajouter les moitiés entières des deux nombres, puis d'ajouter à la fin le bit faible manquant, quand il est pertinent c'est à dire présent dans les deux nombres). Maintenant, avoir un tableau de plus de 2 milliards d'entiers à trier en mémoire est un cas exceptionnel et on peut s'interroger sur le modèle de données utilisé dans l'appli qui aurait besoin de faire ça !

Dernière note (hors sujet mais fait suite à une remarque ci-dessus): Java n'est certainement pas "lent" comme le prétendent encore bon nombre de gens qui ne l'ont pas essayé. Les tests de performance montrent qu'il peut pratiquement égaler le C++ et souvent dépasser .Net, car le code est réellement compilé et optimisé directement sur la machine cible, et pas du tout interprété. Les machines virtuelles se sont énormément améliorées (c'est aussi le cas de .Net qui rattrape son retard, ou de Python et PHP avec le moteur Zend) et cette façon de produire l'environnement d'exécution permet de dépasser les performances qu'on obtiendrait avec une précompilation générique (de type C/C++ ou même assembleur) en faveur d'une seule machine théorique. Aujourd'hui la grande variété des architectures et le fait qu'on est amené à réinstaller le même code de l'une à l'autre, milite en faveur des machines virtuelles à compilation dynamique (comme Java, .Net, Python, PHP/Zend, ...) dont les performances et la portabilité est nettement supérieure (et demande également beaucoup moins d'effort de la part du programmeuir qui n'a besoin de concevoir son programme qu'une seule fois avec une base solide). Java est aujourd'hui aussi rapide que C++, et souvent plus rapide sur des applications gourmandes en communications ou en volume de données traitées, ou en requêtes, ou en threads, ceci grace à un modèle mémoire plus évolué et plus adapté à un contexte très dynamique. C'est la raison pour laquelle Java marche tellement bien pout les applications multitiers, où il apporte aussi une grande sécurité (qui reste toujours à démontrer pour les applis en C++, les compilateurs C++ ne pouvant pas tout détecter car le langag eest trop permissif).

 Ajouter un commentaire


Discussions en rapport avec ce code source dans le forum

transformer algorithme en java [ par skyfrozen ] Salut tlm je suis vraiment nouveau nouveau à la programmation. j'ai récemment écrit un algorithme pour calculer les ventes d&#8217;un produit en part Implémentation d’un algorithme de conversion d’une image en niveaux de gris en image binaire [ par mainda ] salut à tous,je veux une implementation d'un algorithme de conversion d’une image en niveaux de gris en image binaire selon un seuil optimal à extrair l'algorithme id3 [ par imaneinfo1 ] salut j'ai trouve sur ce site un exemple de l'algorithme id3 mais vous avez utilisé un fichie texte pour stocker la table ma question est si on peut r utilisation d'un script de tri [ par claviskass ] Bonjours a tous Étant infographiste et n&#8217;ayant peu ( vraiment peu ) de connaissance en JavaScript, je sollicite votre aide. On ma envoyé [URL= similateur d'algorithme de cryptographie [ par abdelmajidi4 ] salut, je cherche un algorihme en java qui implemente une interface graphique d'un similateur de cryptographie et merci et j'attend vos répenses d tri de vecteur des vecteur [ par infogoss ] bonjour j'ai un vecteur qui contient des vecteurs . je veux trier les vecteur selon la dernière case. la taille de grand vecteur est: Nindv alors Algorithme de recherche [ par Taz1984 ] Bonjour, j'ai un tableau qui contient 10000 cases de chaines de caractères. Lorsque je recherche un élément dans ce tableau, je suis obligé de parc l'implémentation de l'algorithme de powell (arbre) dans un programme Java. [ par ayoubbabanou ] bonjour tout le monde, j'ai un projet de fin d'étude sur "Gestion d'emploi du temps dans un établissement scolaire" avec une application Java. J'ai fa Programmation d'un algorithme de colonies de fourmis [ par sabrinafr ] bonjour, j'ai un soucis concernant l'implementation du comportement des fourmis au sein d'une colonie, je m'interesse uniquement par la capacité des


Nos sponsors


Sondage...

Comparez les prix

CalendriCode

Février 2012
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
272829    

Consulter la suite du CalendriCode

 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 0,842 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales