Accueil > > > TRI TABLEAU D'INTEGER PAR DICHOTOMIE, MAJ
TRI TABLEAU D'INTEGER PAR DICHOTOMIE, MAJ
Information sur la source
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;
}
}
Sources du même auteur
Sources de la même categorie
Commentaires et avis
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’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
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
|
Derniers Blogs
UNE JOLIE-HORLOGE ET PAS QU'UN PEU !UNE JOLIE-HORLOGE ET PAS QU'UN PEU ! par neodante
Pour les possesseurs d'iPhone, ça y est Bijin Tokei - qui se traduit littéralement en Français par " Jolie Horloge " - est arrivé et GRATUITEMENT s'il vous plaît ! Après la version Tokyo, Hokkaido, night club, racing, Gal, "pour les mademoiselles'", . voi...
Cliquez pour lire la suite de l'article par neodante TECHDAYS PARIS 2010 : CONNECTEZ VOS DONNéES à SHAREPOINT 2010 AVEC LES BUSINESS CONNECTIVITY SERVICESTECHDAYS PARIS 2010 : CONNECTEZ VOS DONNéES à SHAREPOINT 2010 AVEC LES BUSINESS CONNECTIVITY SERVICES par ROMELARD Fabrice
Animé par: Gaetan Bouveret et Julien Chomarat Business Connectivity Services (BCS) est dans SharePoint 2010 la version 2 de Business Data Catalog (BDC dans SharePoint 2007). Il s'agit de la solution permettant de visualiser des données provenan...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice [DIVERS] SUIVRE VOS SéRIES PRéFéRéS SUR LA TOILE[DIVERS] SUIVRE VOS SéRIES PRéFéRéS SUR LA TOILE par orion
Comme de nombreux geek, je suis un grand amateur de série TV et je rate régulièrement des épisodes de mes séries préférés. Une solution s'offre à vous avec ce merveilleux site : Tv Gorge - www.tvgorge.com Moteur de recherche à l'appui, vous pouvez ...
Cliquez pour lire la suite de l'article par orion TECHDAYS PARIS 2010 : LA BI DANS SHAREPOINT 2010TECHDAYS PARIS 2010 : LA BI DANS SHAREPOINT 2010 par ROMELARD Fabrice
Animé par: Vincent Bellet et Baptiste Giraudier La BI dans SharePoint 2010, Les nouveaux services d'application dans SP2010 et SQL Server Reporting services 2008 R2. La BI dans SharePoint est généralisée pour tous afin de permettre à tous les coll...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice
Logiciels
DB-MAIN (9.1.0)DB-MAIN (9.1.0)DB-MAIN is a data-modeling and data-architecture tool. It is designed to help developers and anal... Cliquez pour télécharger DB-MAIN Xilisoft DPG Convertisseur (5.1.37.0120)XILISOFT DPG CONVERTISSEUR (5.1.37.0120)Xilisoft DPG Convertisseur offre aux fans de Nintendo DS une bonne solution leur permettant de dé... Cliquez pour télécharger Xilisoft DPG Convertisseur GraphicsGale (2.01.01)GRAPHICSGALE (2.01.01)GraphicsGale est un logiciel de PixelArt avec de nombreuse fonctionnalités permettant de réalisé ... Cliquez pour télécharger GraphicsGale Architecte 3D (Platinum 2010)ARCHITECTE 3D (PLATINUM 2010)Architecte 3D Platinium vous permet de concevoir facilement les plans votre future maison, de l'é... Cliquez pour télécharger Architecte 3D TeamViewer 5 (TeamViewer 5)TEAMVIEWER 5 (TEAMVIEWER 5)Dépanner un ami,expliquer une manipulation devient un jeu d'enfant.
Prise en main d'un autre ord... Cliquez pour télécharger TeamViewer 5
|