Trie :selection Ordinaire,selection Bulle,insertion Ordinaire,insertion Dichotom

Signaler
Messages postés
15
Date d'inscription
mardi 3 mars 2009
Statut
Membre
Dernière intervention
26 juin 2009
-
Messages postés
15814
Date d'inscription
jeudi 8 août 2002
Statut
Modérateur
Dernière intervention
4 mars 2013
-
Bonjour,
Je tenais à contribuer au partage de code source en mettant se que j'ai fait avec mon binome sur les algorithmes de tri. Je pense qu'il soit bien codé et optimisé.

package Algorithmes;

import java.util.Arrays;

public class TriEntier {

// TRI SELECTION ORDINAIRE
public static void selectionOrdinaire(int[] T){
long debut = System.currentTimeMillis();

int i,j,valeur,index;
int indexAjout=0;
int tailleT=T.length;

while(indexAjout<taillet-1){ valeur="T[indexAjout];" index="indexAjout;" for(i="indexAjout;i<tailleT;i++){" if(valeur="">T[i]){
valeur=T[i];
index=i;
}
}

for(j=index;j>indexAjout;j--)
T[j]=T[j-1];
T[indexAjout]=valeur;
indexAjout++;
}

long duree = System.currentTimeMillis() - debut;
System.out.println("TRI SELECTION ORDINAIRE Temps d'exécution : " + (float)duree/1000 + " secondes");
}

// TRI INSERTION BULLE
public static void selectionBulle(int[] T) {
long debut = System.currentTimeMillis();

int temp,dernierePermut;
int fin = T.length-1;
do {
dernierePermut = -1;
for (int i = 0; i < fin; i++) {

if (T[i] > T[i + 1]) {
temp = T[i];
T[i] = T[i + 1];
T[i + 1] = temp;
dernierePermut = i;
}
}
fin = dernierePermut;
} while (dernierePermut!=-1);
long duree = System.currentTimeMillis() - debut;
System.out.println("TRI SELECTION BULLE Temps d'exécution : " + (float)duree/1000 + " secondes");
}

// TRI INSERTION ORDINAIRE
public static void insertionOrdinaire(int[] T){
long debut = System.currentTimeMillis();

int index,j,k,temp;

for(index = 1;index < T.length; index++){
if(T[index-1]>T[index]){
temp = T[index];
j=0;
while (T[j]<temp) j++;="" for(k="index;k">j;k--){
T[k]=T[k-1];
}
T[j]=temp;
}
}

long duree = System.currentTimeMillis() - debut;
System.out.println("TRI INSERTION ORDINAIRE Temps d'exécution : " + (float)duree/1000 + " secondes");

}

// TRI INSERTION DICHOTOMIQUE
public static void insertionDichotomique(int[] T){
long debut = System.currentTimeMillis();

int index,borneInf,borneSup,mil,i,temp;

for(index = 1;index < T.length; index++){
if(T[index-1]>T[index]){
temp = T[index];
borneInf = 0;
borneSup = index;
mil = (borneSup-borneInf)/2;
while(borneInf!=mil){
if(T[index]>T[mil])
borneInf = mil;
else
borneSup = mil;
mil = (borneSup-borneInf)/2 + borneInf;
}

if(T[mil]>temp){
for(i=index;i>mil;i--)
T[i]=T[i-1];
T[mil]=temp;
}
else{
for(i=index;i>mil+1;i--)
T[i]=T[i-1];
T[mil+1]=temp;
}
}
}
long duree = System.currentTimeMillis() - debut;
System.out.println("TRI INSERTION DICHOTOMIQUE Temps d'exécution : " + (float)duree/1000 + " secondes");
}

// TRI RAPIDE
public static void triRapide(int[] T) {
long debut = System.currentTimeMillis();
int deb = 0;
int fin = T.length-1;
triRapide(T, deb, fin);
long duree = System.currentTimeMillis() - debut;
System.out.println("TRI RAPIDE Temps d'exécution : " + (float)duree/1000 + " secondes");
}

private static void echanger(int T[], int a,int b){
int temp = T[a];
T[a] = T[b];
T[b] = temp;
}

private static void triRapide(int[] T, int deb, int fin) {
if (deb < fin) {
int pivot = partitionner(T, deb, fin);
triRapide(T, deb, pivot);
triRapide(T, pivot+1, fin);
}
}

private static int partitionner(int[] T, int deb, int fin) {
int pivot = (fin+deb)/2;
echanger(T, deb, pivot);
int index = deb;
for (int i = deb+1; i<= fin; i++) {
if (T[i] < T[deb]) {
index++;
echanger(T, i, index);
}
}
echanger(T, deb, index);
return index;
}


// TRI PAR TAS
public static void triParTas(int[] T){
long debut = System.currentTimeMillis();
for(int i=(T.length-1)/2; i>=0;i--){
ordonner(T,i,(T.length-1));
}
for(int i= T.length-1; i>=1;i--){
int temp1,temp2=0;
temp1=T[0];
temp2=T[i];
T[i]=temp1;
T[i]=temp2;
ordonner(T,0,i-1);
}
long duree = System.currentTimeMillis() - debut;
System.out.println("TRI PAR TAS Temps d'exécution : " + (float)duree/1000 + " secondes");
}

private static void ordonner (int[] T,int rac, int fin){
int fils=0;
int pere=rac;
int u=T[rac];
while(pere*2<=fin){
fils=pere*2;
if(T[fils]</temp)></taillet-1){>

1 réponse

Messages postés
15814
Date d'inscription
jeudi 8 août 2002
Statut
Modérateur
Dernière intervention
4 mars 2013
126
Salut,

Merci, mais tu devrais plutôt le poster dans la section codes-sources du site, ainsi tu pourra en faire profiter à plus de monde.
______________________________________
DarK Sidious