Exercice sur tableau trié dynamique

Version imprimable

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:

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.

06/07/2011, 14h41
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.
06/07/2011, 14h53
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 :)
06/07/2011, 16h08
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)
06/07/2011, 16h50
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.

Citation:

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.
06/07/2011, 17h17
-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...

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:

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

Il y a 5 erreurs dans ton programme :

Code:

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.

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

Code:

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:

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)

07/07/2011, 13h43
-gma-

Citation:

Envoyé par Johnny P.

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

Citation:

Envoyé par Johnny P.

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

J'avoue ne pas tout saisir :roll:
07/07/2011, 14h26
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.
07/07/2011, 23h52
-gma-

Citation:

Envoyé par thierryler

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.

Citation:

Envoyé par thierryler

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" ?
08/07/2011, 07h36
thierryler

Je veux dire une liste en partie triée.