[Débutant] Tri par insertion
Bonjour,
Je débute l'algorithmie avec le livre "Introduction to algorithms de T.H. Cormen" 3ème édition.
En patientant de m'acheter le livre en Français, je débute donc sur cette référence en Anglais.
Par contre je n'ai que très peu base en algorithmie et du coup je suis un peu perdu avec la syntaxe.
Dans le premier algo : chapitre 2.1 Insertion sort :
On parle bien de tri par insertion ? C'est à dire comme dans l'exemple des cartes où je tire une carte d'une pile posée sur une table puis la place dans ma main vide la première fois. Ensuite je tire une 2ème carte de la pile que je compare avec mon autre carte. Si cette 2ème carte est plus petite que ma 1ère alors je la place à gauche de celle-ci, sinon elle reste à droite. Ensuite je tire une 3ème carte que je compare avec mes 2 autres et je la place de manière à avoir un tri ascendant. Et ainsi de suite... Donc au final selon le nombre de cartes de la pile que j'ai tiré et qui est maintenant dans ma main, j'ai une suite ascendante de carte.
On est bien dans un tri par insertion. Et c'est là où j'ai besoin d'une première aide pour la suite, car dans le cours ils parlent d'un tableau qui a un nombre d'élément : A[1 .. n] -> The algorithm sorts the input numbers in place: it rearranges the numbers within the array A, with at most a constant number of them stored outside the array at any time.
D'une part celà veut dire que le tableau à déjà un nombre d'élément à l'intérieur comme dans la suite : A = (5, 2, 4, 6, 1, 3) Donc on n'est pas dans un tri par insertion là ? On est dans un tri d'élément connu, ou alors il faut imaginer qu'on aura un programme qui donne un nombre d'éléments au tableau, pour que celui-ci soit trié après ? Mais si c'est le cas ce n'est pas trié comme dans l'exemple des cartes.
D'autre part je ne comprend pas cette phrase : " it rearranges the numbers within the array A, with at most a constant number of them stored outside the array at any time." Je la traduit comme : "l'algorithme trie les numéros entrée sur place, il réarrange les numéros à l'intérieur du tableau A, avec au plus un nombre constant de ces numéros en dehors du tableau à n'importe quel moment." C'est surtout la fin de la phrase qui me chagrinne, je ne comprend vraiment pas "avec au plus un nombre constant de ces numéros en dehors du tableau à n'importe quel moment".
Donc pour l'exercice :
1 2 3 4 5 6
(a) 5 2 4 6 1 3
// flèche grise: 5 vers 2, flèche noire : 2 vers 5
(b) 2 5 4 6 1 3
// flèche grise: 5 vers 4, flèche noire : 4 vers 5
(c) 2 4 5 6 1 3
// flèche noire : 6 vers 5
(d) 2 4 5 6 1 3
// flèches grise: 2 vers 4, 4 vers 5, 5 vers 6, 6 vers 1, flèche noire : 1 vers 2
(e) 1 2 4 5 6 3
// flèches grise: 4 vers 5, 5 vers 6, 6 vers 3, flèche noire : 3 vers 4
(f) 1 2 3 4 5 6
The operation of INSERTION-SORT on the array A = (5, 2, 4, 6, 1, 3). Array indices
appear above the rectangles, and values stored in the array positions appear within the rectangles.
(a)–(e) The iterations of the for loop of lines 1–8. In each iteration, the black rectangle (caractère gras)holds the
key taken from A[j], which is compared with the values in shaded rectangles (souligné) to its left in the test of
line 5. Shaded arrows show array values moved one position to the right in line 6, and black arrows
indicate where the key moves to in line 8. (f) The final sorted array.
Ensuite on à l'algorithme :
INSERTION-SORT. A
Figure 2.2 shows how this algorithm works for A = (5, 2, 4, 6, 1, 3). The index1 for j = 2 to A.length 2 key = A[j] 3 // Insert A[j] into the sorted sequence A[i .. j -1] 4 i = j - 1 5 while i>0 and A[i] > key 6 A[i + 1] = A[i] 7 i = i - 1 8 A[i + 1] = key
j indicates the “current card” being inserted into the hand. At the beginning
of each iteration of the for loop, which is indexed by j , the subarray consisting
of elements A[1 .. j - 1] constitutes the currently sorted hand, and the remaining
subarray A[j + 1 .. n] corresponds to the pile of cards still on the table. In fact,
elements A[1 .. j - 1] are the elements originally in positions 1 through j - 1, but
now in sorted order.
Voici comment je comprends l'algo :
- on démarre une boucle for avec un indice j = 2 compris dans un tableau A de 6 éléments
- une variable key vaut A[2]
- commentaire insertion A[2] dans le tri de séquence A[1 .. j - 1]
- une variable i vaut 2 - 1 // donc 1
- boucle while : tant que 1 > 0 et que A[1] > A[2] // true false donc on n'entre pas dans while
- alors A[1 + 1] = A[1] // ici ma compréhension : A[1]
- 1 = 1 -1 // donc 0 ?
8 on retourne ? à la sortie de while A[1 + 1] = A[2] // donc A[2]
Bref j'essaie de comprendre mais c'est très tordu.
Qui aurait la patiente de m'expliquer (Bien sur en regardant sur le livre parce que j'ai copié comme j'ai pu l'exemple)
Et si possible de remplacer cet algo en php avec lequel je suis habitué.
Merci !!
Répondre avec citation
Partager