Discussion :

[Johnny P.]

Bonjour ,

Je suis entrain de faire un exercice qui me semblait pas si difficile que cela , et après des heures je ne parviens toujours pas à une solution ,
le but est de trier un tableau dés qu'on ajoute un élément , on décale le reste et on insère le chiffre ou sinon on ajoute à la fin.

voici ce que j'ai fais

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
public class table {
 
   public static void main(String[] args) {
 
        int tableau[]=new int[7];
		int tabclient[]={10,13,10,11,21,24,11,13,18};
		int i,j,k,dim;
		boolean verif;
 
		k=0;
 
		for(i=0; i<9; i++) {
 
			verif=false;
 
			for(j=0; j<=k && verif !=true; j++) {
 
				if(tabclient[i] != tableau[j]) {
 
					if(tabclient[i] < tableau[j]){
 
						dim=k+1;
 
						while(dim>k) {
 
							tableau[dim]=tableau[dim-1];
							dim--;
 
						}
 
						tableau[j]=tabclient[i];
						k++;
						verif=true;
 
					}
 
				}
				  /*pour après*/
                                  if(tabclient[i]==tableau[j]) {
 
 
					verif=true;
				}
			}
 
			if(verif!=true) {
 
				k++;
				tableau[k]=tabclient[i];
 
			}
 
		}
 
		for(i=0; i<7; i++)
		         System.out.print(tableau[i] + " ");
 
 
       }
 
}

Voilà ce qu'il m'affiche 0 10 11 13 18 24 24 plutôt que 10 11 13 18 21 24
Merci pour tout aide.

[NicoL__]

Ton code n'est pas évident à lire... donc je ne l'ai pas lu.
Si tu veux le bon resultat utiliser un java.util.TreeSet<Integer> ça fera tout le boulot ;-) ça serait le réponse d'un programmeur java. Après si l'exercice c'est de faire des algo... c autre chose.

[pigpen]

Hello,

Ta solution me parait bien complexe, s'agit il d'un problème d'algo ou de JAVA ?
Si il s'agit de JAVA, comme dit précédemment, java.util.TreeSet<Integer> fera tout le boulot

[Ivelios]

ça ne serait pas un "tri par insertion" ton truc?
Si oui regarde ici
Pourquoi utiliser 2 tableaux? Es ce une contrainte?

Et le zéro au début c'est normal, tu entre 6 valeurs dans un tableau de 7 cases... normal qu'il y est une case "vide" (à zéro)

[Johnny P.]

Je ne connais pas java.util.TreeSet<Integer> , je suis assez nouveau dans le monde du Java mais je vais y jeter un coup d'oeil.

Ce n'est pas un tri normal , je connais le tri par insertion ici le but n'est pas de trier un tableau mais bien de recopier une valeur dans un autre tableau en triant le tableau si cette valeur est plus petite à l'ajout d'une nouvelle et sans recopier les doublons.
Il s'agit d'un entraînement algorithmique.
j'essaie de trouver le meilleur moyen de faire sans parcourir le tableau plusieurs fois , sinon ça aurait été trop facile.

Et le zéro au début c'est normal, tu entre 6 valeurs dans un tableau de 7 cases... normal qu'il y est une case "vide" (à zéro)

En effet je l'ai remarqué c'était pour entrer dans la boucle.

[-gma-]

Bonjour,

Pour la partie "recherche de la position où insérer la nouvelle valeur dans le tableau déjà trié" il y a la méthode Arrays.binarySearch(int[], int) qui permet de faire ça par recherche dichotomique. Si tu ne veux pas l'utiliser tu peux toujours t'inspirer de l’implémentation de ton JDK...

[Johnny P.]

Le tableau n'est pas trié obligatoirement donc la rechercher dichotomique est à éviter.

Actuellement je suis arrivé à ce stade mais j'ai un problème à trouver pourquoi le 21 n'est pas ajouté

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public class table {
 
   public static void main(String[] args) {
 
        int tableau[]=new int[6];
		int tabclient[]={11,13,3,11,21,24,11,13,18};
		int i,j,k=0,dim;
		boolean verif;
 
		for(i=0; i<9; i++) {
 
			verif=false;
 
			for(j=0; j<=k && verif !=true; j++) {
 
				if(tabclient[i] != tableau[j]) {
 
					if(tabclient[i] < tableau[j]) {
 
						dim=k+1;
 
						while(dim>k) {
 
							tableau[dim]=tableau[dim-1];
							dim--;
 
						}
 
						tableau[j]=tabclient[i];
						k++;
						verif=true;
 
					}
 
				}
 
				if(tabclient[i]==tableau[j]) {
 
 
					verif=true;
				}
 
			}
 
		if(verif!=true && k<6) {
 
			       tableau[k]=tabclient[i];  
 
			}
 
		}
 
		for(i=0; i<6; i++)
		         System.out.print(tableau[i] + " ");
 
 
       }
 
}

J'ai ceci 3 11 13 18 24 0 plutôt que 3 11 13 18 21 24

[Ivelios]

Il y a 5 erreurs dans ton programme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
public class Table {// Le class avec une MAJUSCULE
 
    public static void main(String[] args) {
 
        int tableau[] = new int[6];
        int tabclient[] = {11, 13, 3, 11, 21, 24, 11, 13, 18};
        int i, j, k = 0, dim;
        boolean verif;
        for (i = 0; i < 9; i++) {
            verif = false;
            for (j = 0; j < k && verif != true; j++) { //1/ au lieu de (j <= k )
                if (tabclient[i] != tableau[j]) {
                    if (tabclient[i] < tableau[j]) {                
                        dim = k + 1;
                        if(dim == 6) dim = 5; //2/ vérifier qu'on ne sort pas du tableau
                        while (dim > j) {//3/ j et pas k, sinon on ne passe qu'une fois dedans
 
                            tableau[dim] = tableau[dim - 1];
                            dim--;
                        }
                        tableau[j] = tabclient[i];
                        k++;
                        verif = true;
                    }
                }
                if (tabclient[i] == tableau[j]) {
                    verif = true;
                }
            }
            if (verif != true && k < 6) {
                tableau[k] = tabclient[i];
                k++;//4/ incrémenter la taille du tableau
            }
        }
        for (i = 0; i < 6; i++) {
            System.out.print(tableau[i] + " ");
        }
    }
}

Je tiens à préciser que ton code est particulièrement illisible, pense au moins à utiliser des noms de variables correct (genre nbElemInTab au lieu de k ou 2 boolean inTab et doublon au lieu de verif) et à commenter un minimum les parties pointilleuses.

Dernière chose :
for(j=0; j<=k && verif !=true; j++) {C'est moche et dur à lire, fait directement un break; dans la boucle.

[thierryler]

Tu peux faire un truc dans ce goût là

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
public class TriDeTableau {
 
	public static final Integer[] TABLEAU_INITIAL = { 11, 13, 3, 11, -5, 21, 24, 11, 13, 18 };
 
	public static Integer[] trierEnJava(Integer[] tab) {
		final TreeSet<Integer> set = new TreeSet<Integer>(Arrays.asList(tab));
		final Integer[] result = new Integer[set.size()];
		set.toArray(result);
		return result;
	}
 
	public static Integer[] trierParAlgo(Integer[] tab) {
 
		final Integer[] result = new Integer[tab.length];
 
		for (Integer item : tab) {
 
			for (int i = 0; i < result.length; i++) {
				if (result[i] == null || item == result[i]) {
					result[i] = item;
					break;
				}
 
				if (item < result[i]) {
 
					// 1) Faire décalage
					for (int j = result.length - 1; i < j; j--) {
						result[j] = result[j - 1];
					}
 
					// 2) Insertion
					result[i] = item;
 
					break;
				}
 
				// sinon on continue
			}
 
		}
 
		return result;
	}
 
	/**
         * @param args
         */
	public static void main(String[] args) {
 
		System.out.println("Tableau de départ");
		for (Integer item : TABLEAU_INITIAL) {
			System.out.println(item);
		}
 
		System.out.println("Tableau trié en Java");
		final Integer[] tableauTrieEnJava = trierEnJava(TABLEAU_INITIAL);
		for (Integer item : tableauTrieEnJava) {
			System.out.println(item);
		}
 
		System.out.println("Tableau trié par algo");
		final Integer[] tableauTrieParAlgo = trierParAlgo(TABLEAU_INITIAL);
		for (Integer item : tableauTrieParAlgo) {
			System.out.println(item);
		}
	}
 
}

J'ai ajouté un chiffre négatif dans la liste de départ pour bien montrer que ça marche.

Et ça donne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
Tableau de départ
11
13
3
11
-5
21
24
11
13
18
Tableau trié en Java
-5
3
11
13
18
21
24
Tableau trié par algo
-5
3
11
13
18
21
24
null
null
null

On voit qu'il y a 3 doublons (ie. 3 nulls)

[-gma-]

le but est de trier un tableau dés qu'on ajoute un élément

Le tableau n'est pas trié obligatoirement donc la rechercher dichotomique est à éviter.

J'avoue ne pas tout saisir

[thierryler]

Il y a deux choses à comprendre.

1) Faire une recherche dichotomique sur un ensemble non trié, ça n'a pas de sens puisque le principe de la dichotomie est de ne garder qu'une moitié de la liste à chaque fois. Si ta liste n'est pas triée, tu ne peux pas savoir quelle partie garder.

2) Ca n'a rien à voir mais tu ne dois surtout pas faire de tri par séparation (comme le quick sort) sur une liste déjà triée.

[-gma-]

1) Faire une recherche dichotomique sur un ensemble non trié, ça n'a pas de sens puisque le principe de la dichotomie est de ne garder qu'une moitié de la liste à chaque fois. Si ta liste n'est pas triée, tu ne peux pas savoir quelle partie garder.

Jusque là ok, c'est évident.

2) Ca n'a rien à voir mais tu ne dois surtout pas faire de tri par séparation (comme le quick sort) sur une liste déjà triée.

Pourquoi trier une liste "déjà triée" ?

[thierryler]

Je veux dire une liste en partie triée.