Ajouter tri rapide

Résolu/Fermé
Signaler
-
 zmandar -
Bonjour,



je créé cette programme en java et je veux ajouter le tri rapide dans le programme
je veux quelqu' un m 'aider



package projet;
import java.io.*;
public class MenuTri
{
static int i,taille;
private static int choix;
public static void main(String[]args)throws IOException
{
BufferedReader valeur=new BufferedReader(new InputStreamReader(System.in));
System.out.println("\t\t\t\t\t\t****un menu de tri****");
System.out.print("Donnez la longueur du Tableau:\t\t");
taille=Integer.parseInt(valeur.readLine());

int T[]=new int[taille];

remplir(T);

System.out.println("***tableau non trie***\n");
afficher(T);

System.out.println("\t\t\t\tentrer votre choix ");
System.out.println("*****tri bulle=1/tri par selection=2/tri par insertion=3/tri par fusion=4*****\n");
int menu =Integer.parseInt(valeur.readLine());

switch(menu)
{
case 1:
{
System.out.println("vous avez choisis le tri bulle\n");
tribulle(T);
System.out.println("tableau est trie\n");
afficher(T);
}
break;
case 2:
{
System.out.println("vous avez choisis le tri par selection\n");
triparselection(T);
System.out.println("tableau est trie\n");
afficher(T);


}
break;
case 3:
{
System.out.println("vous avez choisis le tri par insertion\n");
triParinsertion(T,taille);
System.out.println("tableau est trie\n");
afficher(T);


}
break;
case 4:
{
System.out.println("vous avez choisis le tri par fusion\n");
tri_fusion(T,taille);
System.out.println("tableau est trie\n");
afficher(T);


}
case 5:
{
System.out.println("vous avez choisis le tri par rapide\n");
tri_fusion(T,taille);
System.out.println("tableau est trie\n");
afficher(T);
}
break;
default:
System.out.println("erreur\n");
break;
}

}
private static int[] fusion(int[] tab1, int[] tab2)
{int an=0;
int cn=0 ;
int i, i_g=0, i_d=0;
int taille_g=tab1.length, taille_d=tab2.length;

int [] res=new int[taille_g+taille_d];

for(i=0; i_g<taille_g && i_d<taille_d; i++)
{
an++;
if(tab1[i_g] <= tab2[i_d])
{
cn++;
res[i]=tab1[i_g++];
}
else
{
res[i]=tab2[i_d++];
}
}

// on copie le reste du tableau de gauche (s'il reste quelque chose)

while(i_g<taille_g)
{
res[i++]=tab1[i_g++]; // Ne pas oublier le ++ (boucle infinie)
}

while(i_d<taille_d)
{
res[i++]=tab2[i_d++]; // Pareil c'est tab2
}

return res;
}

//*******************************************************************

private static int[] copie(int[] tab, int debut, int fin)
{
int[] res=new int[fin-debut+1];

for(int i=debut; i<=fin; i++)
{
res[i-debut]=tab[i];
}
return res;
}

//*******************************************************************

public static int[] tri_fusion(int[] tab,int taille)
{
if(taille<=1)
return tab;
else
{
int milieu = taille/2;
int[] gauche = copie(tab,0,milieu-1);
int[] droite = copie(tab,milieu,taille-1);

return fusion(tri_fusion(gauche,milieu),
tri_fusion(droite,(taille-milieu)));
}
}

public static int[] triParinsertion(int [] T ,int taille) throws IOException
{
int i;
int memoire=0; // memoire:valeur en cours de traitement
int compteur=0; // indique la partie du tableau à traiter
// faut-il continuer les comparaisons?
int cn=0;
int an=0;
for(i=1; i<taille; i++)
{
memoire =T[i];


for (int k=i+1;k>0;k--){
cn++;
if( T[k-1]>memoire){
an++;
T[k] = T[k-1];
}

}


}T[compteur] = memoire;
System.out.println("le nombre de comaparaison et affectation"+cn+" "+an) ;
return T ;
}

static void tribulle(int T[])
{int an=0 ;
int cn=0;
boolean permut;
int inter;

do
{
permut=false;
for(int i=0;i<taille-1;i++)
{cn++;

if(T[i]>T[i+1])
{an++ ;
inter=T[i];
T[i]=T[i+1];
T[i+1]=inter;
permut=true;

}


}
}
while(permut!=false);
System.out.println("le nombre de comaparaison et affectation"+cn+" "+an) ;
}
public static int[] triparselection (int [] T) throws IOException {
int k=0,inter,pp;
int cn =0;
int j;
int an=0;
for( j=0;j<taille-1;j++)
{
pp=T[j];

for(int i=j+1;i<taille;i++)
{cn++;
if(T[i]<pp)
{an++;

pp=T[i];
k=i;

inter=T[j];
T[j]=pp;
T[k]=inter;
}
}



}
System.out.println("le nombre de comaparaison et affectation"+cn+" "+an) ;
return(T);
}
public static int[] random(int T[],int taille)
{


int i=0;
for( i=0;i<taille;i++){

T[i]=(int)(Math.random() *(512-2)+2);}
return T;


}
public static int[] tableautrié(int T[],int taille)
{ for(int i=0;i<taille;i++){
T[i]=i;
} return(T);

}
public static int[] antitri(int T[],int taille)
{

for (int i=1; i<=taille;i++)
{ T[i-1]= taille-i;}

return(T);}

static void remplir(int T[]) throws IOException
{BufferedReader valeur=new BufferedReader(new InputStreamReader(System.in));
System.out.println("les element du tableau:chois aléatoire=1/trié=2/ anti trié=3 ");
int choix =Integer.parseInt(valeur.readLine());

switch(choix)
{
case 1:
{ System.out.println("les element du tableau sont choisie aleatoirement");
random(T,taille);}
break;
case 2:
{ System.out.println("les element du tableau sont trié");
tableautrié(T,taille);}
break ;

case 3:
{ System.out.println("les element du tableau sont antitrié");
antitri(T,taille);}

default:
System.out.println("erreur\n");
break;
}
}




static void afficher(int T[])
{
for(int i=0;i<taille;i++)
{
System.out.println(T[i]+"\n \t\n");
}
}
}

3 réponses

je le programe de tri rapide qui je veux l 'ajouter


public static void triRapide(int tableau[])
{
int longueur=tableau.length;
triRapide(tableau,0,longueur-1);
}

private static int partition(int tableau[],int deb,int fin)
{
int compt=deb;
int pivot=tableau[deb];

for(int i=deb+1;i<=fin;i++)
{
if (tableau[i]<pivot)
{
compt++;
echanger(tableau,compt,i);
}
}
echanger(tableau,deb,compt);
return(compt);
}

private static void triRapide(int tableau[],int deb,int fin)
{
if(deb<fin)
{
int positionPivot=partition(tableau,deb,fin);
triRapide(tableau,deb,positionPivot-1);
triRapide(tableau,positionPivot+1,fin);
}}
public static void echanger(int tableau[],int l,int k){
int aux=0;
int j=k,i=l;
aux=tableau[i];
tableau[i]=tableau[j];
tableau[j]=aux; }

}
je veux ajouter le deuxième programme au premier programme svp aide moi
svp aide moi