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
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
|
Derniers Blogs
SESSION SILVERLIGHT 5 3D : SLIDES ET DEMOSSESSION SILVERLIGHT 5 3D : SLIDES ET DEMOS par Groc
Durant les techdays, j'ai eu le plaisir d'animer une session sur Silverlight 5 et la 3D avec Simon Ferquel. Comme promis, voici nos slides et mes démos (celles avec le viper BSG) ici et là. Pour mémoire, les démos utilisent toutes le viper BSG...
Cliquez pour lire la suite de l'article par Groc [TECHDAYS 2012] SESSION WEBMATRIX 2 : LE COUTEAU SUISSE GRATUIT POUR VOS DéVELOPPEMENTS WEB - SLIDES[TECHDAYS 2012] SESSION WEBMATRIX 2 : LE COUTEAU SUISSE GRATUIT POUR VOS DéVELOPPEMENTS WEB - SLIDES par gpommier
Suite à la session que j'ai présenté sur WebMatrix 2, vous pouvez trouver les slides ici, ainsi que les démos en packages nuget : démos1 et démos2 J'en profite pour remercier chaleureusement tous ceux qui sont venus très nombreux à cette sess...
Cliquez pour lire la suite de l'article par gpommier [SHAREPOINT] LES SESSIONS TECHDAYS 2012.[SHAREPOINT] LES SESSIONS TECHDAYS 2012. par Patrick Guimonet
Voici donc pour ceux qui n'ont pas pu venir, ou ceux qui n'ont pas pu toutes les suivre la liste des sessions SharePoint aux TechDays 2012, que je mettrais à jour dès que les liens des vidéo seront disponibles. Ou ici : http...
Cliquez pour lire la suite de l'article par Patrick Guimonet TECHDAYS PARIS 2012 : SESSION PLEINIèRE JOUR 3TECHDAYS PARIS 2012 : SESSION PLEINIèRE JOUR 3 par ROMELARD Fabrice
Speaker: Bernard Ourghanlian Cette session est comme chaque jour transmise en live par BrainSonic, et j'ai donc suivi cette troisième pleinière par ce moyen sur mon iPad . Elle est dédiée comme chaque année à la mise en perspective de l'é...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice MISHRA READER : UN LECTEUR RSS TRèS ZUNE STYLE EN OPEN SOURCE !MISHRA READER : UN LECTEUR RSS TRèS ZUNE STYLE EN OPEN SOURCE ! par Vko
Hier durant une session dédiée aux Techdays 2012, j'ai eu le plaisir d'annoncer la sortie de la Béta 2 de Mishra Reader. C'est quoi ? Pour les utilisateurs, c'est une vraie expérience de lecture de flux RSS sur Windows. Rien à voir avec les produit...
Cliquez pour lire la suite de l'article par Vko
Forum
AIDEAIDE par mlawah
Cliquez pour lire la suite par mlawah RE : J2EERE : J2EE par issats1987
Cliquez pour lire la suite par issats1987 RE : J2EERE : J2EE par abdouffff
Cliquez pour lire la suite par abdouffff RE : J2EERE : J2EE par issats1987
Cliquez pour lire la suite par issats1987
Logiciels
Academy System (17.2.1.0)ACADEMY SYSTEM (17.2.1.0)Logiciel de gestion des établissements.
- élèves/étudiants (inscription, dossier, absence...)
-... Cliquez pour télécharger Academy System Easy-Planning (1.0.0.1)EASY-PLANNING (1.0.0.1)Basé sur les mêmes principes que MyPlanning, Easy-Planning permet de créer des plannings sous la ... Cliquez pour télécharger Easy-Planning COLLECTOR PLUS (3.00B)COLLECTOR PLUS (3.00B)COLLECTOR PLUS version 3.00B est un logiciel utilisant une base de données alimentée par :
- L... Cliquez pour télécharger COLLECTOR PLUS PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V7.4)PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V7.4)PONAMEDIA TV DEVIENS HELLLOOO FLASH
LA TV SUR VOTRE ORDINATEUR.
Toute une plateforme Multi... Cliquez pour télécharger PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO LettresFaciles 2011 (8.0.0.1)LETTRESFACILES 2011 (8.0.0.1)LettresFaciles est un logiciel facilitant la création et la rédaction de lettres types.
Son inte... Cliquez pour télécharger LettresFaciles 2011
|