Sujet Précédent Sujet Suivant

Ordre croissant

Fermé
ed - 31 oct. 2014 à 22:18
 ed - 1 nov. 2014 à 19:05
Bonjour,

Mon problème n'est pas tellement sur le tri croissant.

Voila, j'ai un vecteur qui contient des valeurs aléatoires par exemple vect=[-12,23,41,-5,10]
je veux n'avoir que les nombres positif de vect et les mettre dans un nouveau vecteur vectTri[]
par ordre croissant.

ici je cherche les valeurs positives et les met dans vecteur tempo. j'incrémente j pour avoir le nombre de valeurs que j'aurais 
 public static int[] newVect(int tab[]){
        
         int longueur,i,j=0;
	 int tampon;
	 boolean permut;
        
        longueur=tab.length;
        
        int[] vectTempo = new int[longueur];
          
        for(i=0;i<longueur;i++){  
            if(tab[i]>0){
                // on rempli tempo avec les valeurs positives de tab
                  vectTempo[j]=tab[i]; 
                  j++;
            }
        }

par la suite
ici j'effectue mon tri croissant. mais les valeurs que j'ai dans le vecteur vectTri n'est pas ce que je doit avoir, car déjà vectTempo a la taille de tab donc quand je ne prend que les valeurs positives, la taille de vectTempo ne sera plus celle de tab et les cases vides seront rempli avec "0" et quand je fait le tri il prend en compte ces case vides et j'ai plus le tri 

     int[] vectTri = new int[j];
          
            do {
			// hypothèse : le tableau est trié
			permut = false;
			for (i = 0; i < j; j++) {
				// Teste si 2 éléments successifs sont dans le bon ordre ou non
				if (vectTempo[i] > vectTempo[i + 1]) {
					// s'ils ne le sont pas, on échange leurs positions
					tampon = vectTempo[i];
					vectTempo[i] = vectTempo[i + 1];
					vectTempo[i + 1] = tampon;
					permut = true;
				}
			}
		} while (permut);

    for(i=0;i<j;i++){
            vectTri[i]=vectTempo[i]; // Afin de ne garder que les nombres triés par ordre croissant dans le vecteur vectTri.
        }
        
        return vectTri;



le code total est: 

     public static int[] newVect(int tab[]){
        
         int longueur,i,j=0;
	 int tampon;
	 boolean permut;
        
        longueur=tab.length;
        
        int[] vectTempo = new int[longueur];
          
        for(i=0;i<longueur;i++){  
            if(tab[i]>0){
                // on rempli tempo avec les valeurs positives de tab
                  vectTempo[j]=tab[i]; 
                  j++;
            }
        }
        
        int[] vectTri = new int[j];
          
            do {
			// hypothèse : le tableau est trié
			permut = false;
			for (i = 0; i < j; j++) {
				// Teste si 2 éléments successifs sont dans le bon ordre ou non
				if (vectTempo[i] > vectTempo[i + 1]) {
					// s'ils ne le sont pas, on échange leurs positions
					tampon = vectTempo[i];
					vectTempo[i] = vectTempo[i + 1];
					vectTempo[i + 1] = tampon;
					permut = true;
				}
			}
		} while (permut);
            
            for(i=0;i<j;i++){
            vectTri[i]=vectTempo[i]; // Afin de ne garder que les nombres triés par ordre croissant dans le vecteur vectTri.
        }
        
        return vectTri;
    }

1 réponse

Réponse 1 / 1
KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 3 015
31 oct. 2014 à 22:31
Bonjour,

Un début de solution, très simple, tu modifies ta première méthode pour qu'elle te renvoie un tableau avec le bon nombre de cases, cela t'évites tout tes problèmes lié à la gestion des cases vides.

Exemple : 

public static int[] retainPositive(int[] tab)
{
    if (tab==null)
        return null;

    int sz=0;
    for (int n : tab)
        if (n>0)
            sz++;
    
    int[] res = new int[sz];
    
    int i=0;
    for (int n : tab)
        if (n>0)
            res[i++]=n;
    
    return res;
}
0
ed
31 oct. 2014 à 23:46
voici le code que j'ai modifier.
je commence par trier pas ordre croissant puis je recherche les positifs en incrémentant un indice qui me donne le nombre de valeur positif, j'utilise donc cet indice pour crée le nouveau vecteur avec comme taille l'indice 

public static int[] newVect(int tab[]){
        
         int longueur,i,j=0,k=0,tmp;
       
        longueur=tab.length;
        int[] vectTempo = new int[longueur];
        
				for(i=0; i<longueur-1; i++){
					if(tab[i]>tab[i+1]){
						tmp=tab[i];
						tab[i]=tab[i+1];
						tab[i+1]=tmp;
					}	
				}
                                
         System.out.println(Arrays.toString(tab));
         
        for(i=0;i<longueur;i++){  
            if(tab[i]>0){
                vectTempo[i]=tab[i];
                  j++;
            }
        }
        System.out.println(Arrays.toString(vectTempo));

        int[] vectTri = new int[j];
    
            for(i=0;i<longueur;i++){
                if(vectTempo[i]!=0){
            vectTri[k]=vectTempo[i];
            k++;
        }
       }
        
        return vectTri;
    } 
    
}
0
KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 3 015
1 nov. 2014 à 12:02
"je commence par trier pas ordre croissant"
Le code que tu as donné ne trie pas tout ! Exemple, [2, 1, 0] va être "trié" en [1, 0, 2]. 

for(i=0; i<longueur-1; i++){
    if(tab[i]>tab[i+1]){
        tmp=tab[i];
        tab[i]=tab[i+1];
        tab[i+1]=tmp;
    }       
}

Il serait d'ailleurs miraculeux d'obtenir un tri en O(n), les meilleurs tris sont en O(n.log n), même si pour un débutant tu auras un tri en O(n²). C'est à dire que si tu as n=10 cases dans ton tableau tu feras "environ" n²=100 comparaisons.

C'est pour ça qu'il est une très mauvaise idée de faire le tri avant de réduire la taille du tableau.
En effet quitte à faire un tri en O(n²) autant réduire n autant que possible. Si tu as n=10 cases dans ton tableau, mais seulement p=5 valeurs positives, il vaut mieux faire un tri qui va te coûter p²=25 comparaisons plutôt que le tri global qui va te coûter n²=100.
Réduire le tableau te coûte O(2n), que tu le fasses avant ou après le tri, tu as donc le choix, trier puis réduire pour un coût de O(n²+2n) ou réduire puis trier pour un coût de O(p²+2n)... sachant que p ≤ n
0
ed
1 nov. 2014 à 17:44
Je comprend ce que tu veux dire, je vais revoir ça et réduire avant de trier
0
ed
1 nov. 2014 à 18:33
Voici les modifications apportées selon ce que tu m'as dit KX 
public static int[] newVect(int tab[]){
        int longueur,i,j=0,k=0,tmp;
       
        longueur=tab.length;
        //je cherche le nombre de nombre positif
        for(i=0;i<longueur;i++){
            if(tab[i]>0)  j++;
        }
        
        //je cree deux vecteur avec la taille = j

        int[] vectTempo = new int[j];
        int[] vectTri = new int[j];
        
        //j'enregistre les nombres positifs danc le vecteur tampon
        for(i=0;i<longueur;i++){
            if(tab[i]>0){
                vectTempo[k]=tab[i];
                k++;
            }
        }
         // je fait le tri du vecteur tampon
        for(i=0; i<j-1; i++){
                if (vectTempo[i] >vectTempo[i+1]) {
                    tmp = vectTempo[i];
                        vectTempo[i] = vectTempo[i+1];
                        vectTempo[i+1]= tmp;
                        }	
		}
        //je recopie dans le vecteur 
        for(i=0;i<j;i++){
            vectTri[i]=vectTempo[i];
       }
        //je retourne le vecteur
        return vectTri;
    }
0
ed
1 nov. 2014 à 18:34
je me rend compte que j'ai plus besoin de vectTri[], je peut juste retourné le vecteur tampon puisqu'il est déjà trier
:p :)
0

Discussions similaires

liste de noms par ordre alphabétique
alma -
alma13 -

23 réponses
Python introuvable
DeepMaze -
mamiemando -

3 réponses
programme qui n'affiche pas le mot secret
EMy.chev -
yg_be -

3 réponses
Formule magique excel??????
sexy_miss -
Raymond PENTIER -

13 réponses
Tri les lettres d'un mot par ordre alphabétique
labejau37 -
DjiDji59430 -

9 réponses