Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

TRI TABLEAU D'INTEGER PAR DICHOTOMIE, MAJ


Information sur la source

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é: 3 405 / 114

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

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10

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

Pour les "Membres Club", vous pouvez 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

Commentaires et avis

signaler à un administrateur
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...

signaler à un administrateur
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);

signaler à un administrateur
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).

signaler à un administrateur
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 :)

signaler à un administrateur
Commentaire de robertjul le 20/01/2009 11:16:02 7/10

Merci beaucoup!

signaler à un administrateur
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 !

signaler à un administrateur
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.

signaler à un administrateur
Commentaire de robertjul le 28/02/2009 14:00:57

Merci beaucoup pour ces informations!

signaler à un administrateur
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

ordonner jslider [ par sanpexos ] salut tout le mondeCe que j'aimerais faire c'est afficher quelque chose la première fois que l'on relâche le bouton de la jslider.Et défaire ce que l' tri de fichier [ par estbn04 ] bonjour!voila un petit probleme...j'ai effectuer un listing de tous les fichiers d'un répertoire et de ses sous repertoires..seulement j'aimerais pouv tri de fichier [ par estbn04 ] bonjour!voila un petit probleme...j'ai effectuer un listing de tous les fichiers d'un répertoire et de ses sous repertoires..seulement j'aimerais pouv Recherche d'algorithme de table de hachage [ par jpegg ] Bonsoir,Je recherche un code source me permettant de coder un programme en Java similaire a gperf. Si quelqu un a une solution, ca m arrangerait bien. Création tableau 2 dimensions + tri [DEBUTANT !!] [ par ctof3552 ] slt !je souhaite trier un tableau de vecteurs sur le 2eme élément du vecteur...comment puis je faireex: mon tablo est :[RP125, 38][RP621, 79][RP268, 3 Probleme de vecteur et le tri [ par niicker ] Salujt j'ai besoin de trié des vecteur int et des vecteur par ordre alphabetique j'aimerais avoir la ligne de code pour faire seulement le trie algorithme de l'ombre portée [ par EulaSky ] salut tout le monde!je suis en train de programmer un peu de filtres en java mais je réussi pas à trouver l'algorithme de l'ombre portée. cad insérer Algorithme de la rotation d'une image [ par EulaSky ] voila je cherche l'algorithme de la rotation d'images... je veux pas utiliser celui fourni dans les librairies de java... vous avez pas un petit lien? Probleme ResultSet et tri [ par cocof ] Je requête dans une base Oracle) qui utilise un tri de type Ascii ) avec une clause orderByJe lis le résultat de la requête avec un resultSet qui me methode tri alphabetique [ par javateux ] bonjour, quelqu'un connait-il une methode permettant de trier des string par ordre alphabetique?Merci d'avance


Nos sponsors

Sondage...

CalendriCode

Juillet 2009
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
2728293031  

Consulter la suite du CalendriCode

Téléchargements

Logiciels à télécharger sur le même thème :

Comparez les prix Nouvelle version


LG KP501

Entre 9€ et 159€


Photothèque Nouveau !



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
Temps d'éxécution de la page : 0,702 sec

Google Coop CodeS-SourceS Google Coop CodeS-SourceS


Certaines images présentes sur le site (notament certains avatars) sont issues des collections IconShock, donc si vous souhaitez utiliser ces icons vous devez les acheter, ne les copiez pas et ne utilisez pas dans vos sites et applications sans les avoir commandé.