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
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’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
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.
|
Derniers Blogs
 L'INTERFACE NATURELLE DE WINDOWS PHONE 7 SERIESL'INTERFACE NATURELLE DE WINDOWS PHONE 7 SERIES par odewit
La tendance est aux interfaces naturelles (NUI), et le keynote de Bill Buxton au MIX l'a bien souligné.
La charte graphique et ergonomique de Windows Phone 7 a donc été entièrement repensée en vue d'obtenir un maximum d'efficacité sur ce point. En re...
Cliquez pour lire la suite de l'article par odewit COMMENT MAPPER UNE VUE SQL SUR UNE COLLECTION DE COMPLEX TYPE?COMMENT MAPPER UNE VUE SQL SUR UNE COLLECTION DE COMPLEX TYPE? par Matthieu MEZIL
Avec EF, les vues doivent être mappées sur des entity types. Le problème c'est que les entity types doivent avoir une clé. Avec EF, nous avons les complex type qui n'ont pas de clé mais les vues ne peuvent pas être mappées dessus. Avec EF4, il est possibl...
Cliquez pour lire la suite de l'article par Matthieu MEZIL [WF4] UN BINDING ACTIVITY/ACTIVITYDESIGNER QUI PASSE MAL?[WF4] UN BINDING ACTIVITY/ACTIVITYDESIGNER QUI PASSE MAL? par JeremyJeanson
Certain d'entre vous on peut être vécu cette situation embarrassante après quelques temps passer avec WF4 : Au début avec mon " ActivityDesigner" , tout allait bien. Et puis un jour j'ai au des problèmes de " Binding" . Alors nous sommes allé sur le site ...
Cliquez pour lire la suite de l'article par JeremyJeanson
Logiciels
 Academy System (10.9.4.0)ACADEMY SYSTEM (10.9.4.0)Logiciel de gestion des établissements.
- élèves/étudiants (inscription, dossier, absence...)
-... Cliquez pour télécharger Academy System Xilisoft Convertisseur Vidéo Ultimate (5.1.39.0305)XILISOFT CONVERTISSEUR VIDéO ULTIMATE (5.1.39.0305)Xilisoft Convertisseur Vidéo Ultimate est un outil puissant de conversion vidéo, facile à utilise... Cliquez pour télécharger Xilisoft Convertisseur Vidéo Ultimate Xilisoft DVD Ripper Ultimate (5.0.64.0304)XILISOFT DVD RIPPER ULTIMATE (5.0.64.0304)Xilisoft DVD Ripper Ultimate est un logiciel excellent pour copier et convertir DVD vers presque ... Cliquez pour télécharger Xilisoft DVD Ripper Ultimate Rigs of Rods (63.3)RIGS OF RODS (63.3)c'est un jeu de multi-simulation camions,autobus voitures, avions, bateaux, hélicoptère avec défo... Cliquez pour télécharger Rigs of Rods
|