Salut à tous. J'aimerai avoir vos lumières sur cet algorithme de tri s'il vous plaît. Tout d'abord je tient a préciser le
but de l'exercice. J'ai une liste de file à implementer et ces files contiennent des entiés. Ces files sont trié par ordre croissant des premiers éléments et par ordre décroissant des derniers éléments. A la fin je dois renvoyer un tabler de type object qui contient le contenu de cette liste. Malheureusement je bloque à un endroit mais je ne vois pas mon erreur. J'ai fait un test avec une table qui contient {3,2,1,6,5,4} et j'obtien {1,2,3,6,5,4}
Il s'agit de liste doublement chaînée.
Voici le code :
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145 public class UnshuffleSort { private ListeDoubleImpl liste; private int nbElement; public UnshuffleSort() { this.liste = new ListeDoubleImpl(); this.nbElement = 0; } /** * tri des elements reçus en parametre * * @param elements * table à trier * @return table contenant les elements tries */ public Object[] trier(Object[] elements) { repartirDonnees(elements); return remplirTableARenvoyer(); } /** * Méthode qui va répartir les éléments contenus dans la table elements dans * les files. * * @param elements */ public void repartirDonnees(Object[] elements) { if (elements.length != 0) { DequeImpl deque = new DequeImpl(); deque.enfilePremier(elements[0]); liste.insererEnTete(deque); nbElement++; for (int i = 1; i < elements.length; i++) { ajouterElements(elements); } } } /** * Cette méthode va ajouter les éléments dans les files par ordre croissant * des premiers éléments de chaque file et par ordre décroissant des * derniers éléments de chaque file i correspond à l'élément qui se trouve * dans la table à l'indice voulu. * * @param i */ public void ajouterElements(Object i) { try { Position p = (Position) liste.premier(); DequeImpl deque = (DequeImpl) p.element(); // On cherche la position d'un deque où l'élément en premier est // plus que grand que i // afin de pouvoir l'y ajouter while ((Integer) i < (Integer) deque.dernier() && (Integer) i > (Integer) deque.premier() && liste.suivant(p) != null) { p = liste.suivant(p); deque = (DequeImpl) p.element(); } // Si i est > que le premier et le dernier du deque alors on // l'insère à la fin. if ((Integer) i > (Integer) deque.dernier() && (Integer) i > (Integer) deque.premier()) { deque.enfileDernier(i); nbElement++; } // Si i est > que le premier et < que le dernier alors on ajoute un // nouveau deque le contenant en fin de liste. if ((Integer) i > (Integer) deque.premier() && (Integer) i < (Integer) deque.dernier()) { // deque = (DequeImpl) liste.insererEnFin(new DequeImpl()); deque = (DequeImpl) this.liste.insererEnFin(new DequeImpl()) .element(); deque.enfilePremier(i); nbElement++; } // Si i est < dernier et que i <= premier on l'insere en tete if ((Integer) i < (Integer) deque.dernier() && (Integer) i <= (Integer) deque.premier()) { deque.enfilePremier(i); nbElement++; } } catch (ListeVideException | FileVideException e) { e.printStackTrace(); } } /** * Méthode qui va permuter les files en comparant les premiers éléments de * celles-ci. Si le 1er élément de file1 > file2 on permute. Sinon on * compare file1 avec le suivant de file2 */ public void permuter() { try { Position p = (Position) liste.premier(); DequeImpl deque = (DequeImpl) p.element(); Position p2 = (Position) liste.suivant(p); while (p2 != null && nbElement < 1) { p2 = (Position) liste.suivant(p); DequeImpl deque2 = (DequeImpl) p2.element(); if ((Integer) deque.premier() > (Integer) deque2.premier()) { liste.permuter(p, p2); deque = (DequeImpl) p.element(); } p2 = liste.suivant(p2); } } catch (ListeVideException | FileVideException e) { e.printStackTrace(); } } public Object[] remplirTableARenvoyer() { Object[] table = new Object[nbElement]; if (table.length <= 1) return table; try { Position p = (Position) liste.premier(); int i = 0; while (!liste.estVide()) { while (!((DequeImpl) p.element()).estVide()) { table[i++] = ((DequeImpl) p.element()).defilePremier(); permuter(); } if (((DequeImpl) p.element()).estVide()) { Position suivant = liste.suivant(p); liste.supprimer(p); p = suivant; } } } catch (ListeVideException | FileVideException e) { e.printStackTrace(); } return table; }
Partager