Discussion :

[Intelego]

Bonjour,


J'étudie l'algorithme par insertion récursif tel que le voici :

Code Java :

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
 
// Recursive function to sort an array using 
    // insertion sort 
    static void insertionSortRecursive(int arr[], int n) 
    { 
        // Base case 
        if (n <= 1) 
            return; 
 
        // Sort first n-1 elements 
        insertionSortRecursive( arr, n-1 ); 
 
        // Insert last element at its correct position 
        // in sorted array. 
        int last = arr[n-1]; 
        int j = n-2; 
 
        /* Move elements of arr[0..i-1], that are 
          greater than key, to one position ahead 
          of their current position */
        while (j >= 0 && arr[j] > last) 
        { 
            arr[j+1] = arr[j]; 
            j--; 
        } 
        arr[j+1] = last; 
    } 
 
    // Driver Method 
    public static void main(String[] args) 
    { 
        int arr[] = {12, 11, 13, 5, 6}; 
 
        insertionSortRecursive(arr, arr.length); 
 
        System.out.println(Arrays.toString(arr)); 
    } 
}

Et je ne comprends pas pourquoi l'auteur utilise cinq fois l'appel de la méthode insertionSortRecursive( arr, n-1 ) ligne 09 ?

Que fait la machine ensuite de ces cinq insertionSortRecursive( arr, n-1 ). Restent-ils dans la mémoire ou bien servent-ils pour déplacer un simple curseur ?

Merci pour toute réponse,

Cordialement,

Nino Adrien.

[AbsoluteLogic]

Salut,

Et je ne comprends pas pourquoi l'auteur utilise cinq fois l'appelle de la méthode insertionSortRecursive( arr, n-1 ) ligne 09 ?

C'est le principe du récursif d'appeler plusieurs fois la fonction.

Au premier appel, cela fait: insertionSortRecursive({12, 11, 13, 5, 6}, 5); (5)
qui appelle insertionSortRecursive({12, 11, 13, 5, 6}, 4); (4)
qui appelle insertionSortRecursive({12, 11, 13, 5, 6}, 3); (3)
qui appelle insertionSortRecursive({12, 11, 13, 5, 6}, 2); (2)
qui appelle insertionSortRecursive({12, 11, 13, 5, 6}, 1); (1)
avec:
(1) qui retourne {[12],11,13,5,6},
(2) qui retourne {[11,12],13,5,6},
(3) qui retourne {[11,12,13],5,6},
(4) qui retourne {[5,11,12,13],6},
(5) qui retourne {[5,6,11,12,13]}.
A chaque fois, c'est les éléments d'indices entre 0 et n-1 (que j'ai mis entre crochets) qui sont triés.

[Intelego]

Merci,

Cependant l'appel cinq fois de la méthode insertionSortRecursive( arr, n-1 ); semble faire que le tableau va être évalué de gauche à droite.

Alors que int last = arr[n-1]; et int j = n-2; (ligne 14) et même j-- (ligne 23) semble faire que le tableau va être évalué (ou les tableaux devrais-je dire selon vous ?) dans le sens contraire, depuis la fin vers le début.

C'est cette contradiction des sens des itérateurs qui me donne l’impression que tout les indices vont se bousculer, que la collision est imminente.

Illusion d'esprit ?

Intelego.

[AbsoluteLogic]

Si tu as mis le sujet en résolu, c'est que tu as compris finalement?

C'est cette contradiction des sens des itérateurs qui me donne l’impression que tout les indices vont se bousculer, que la collision est imminente.

J'ai lu itérateur? Les itérateurs sont justement pour les algorithmes itératifs, or là on est en récursif. Il faut voir les choses de manière plus globale.

Cependant l'appel cinq fois de la méthode " insertionSortRecursive( arr, n-1 ); " semble faire que le tableau va être évalué de gauche à droite.

Le tableau n'est pas "évalué de ... à ...", c'est directement des sous-tableaux "entiers" qui sont considérés: tous les tableaux d'indices 0 à k-1, avec k inférieur à la taille du tableau.

Alors que " int last = arr[n-1];" et " int j = n-2; " (linge 14) et même "j--" (ligne 23) ...

Ces opérations ne correspondent qu'à une étape de récursion, dans laquelle ont doit décaler une partie du tableau pour pouvoir insérer le nouvel élément.

[tbc92]

Dans le code initial, ajoute 2 lignes :
En ligne 8, tu ajoutes [c]print ( "passage ligne 8 n=", n)|/c] et en ligne 13, tu ajoutes [c]print ( "passage ligne 13 n=", n)|/c] Ca devrait t'aider à voir ce qui se passe.

[Intelego]

Salut,

Je viens d'essayer ce que tu proposes tbc92, soit ajouter deux lignes tel que voici :

Code Java :

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

1
2
print ( "passage ligne 8 n=", n);
print ( "passage ligne 13 n=", n);

Cela donne ce code sur netbean si je suis bien :

Code Java :

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
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package insr.java;
 
import java.util.Arrays; 
 
public class insr  { 
    // Recursive function to sort an array using 
    // insertion sort 
    static void insertionSortRecursive(int arr[], int n) 
    { 
        // Base case 
        if (n <= 1) 
            return; 
       print("passage ligne 13 n=", n);
        // Sort first n-1 elements 
        insertionSortRecursive( arr, n-1 ); 
 
        // Insert last element at its correct position 
        // in sorted array. 
     print("passage ligne 13 n=", n);
        int last = arr[n-1]; 
        int j = n-2; 
       // 12, 11, 13, 5, 6 
        /* Move elements of arr[0..i-1], that are 
          greater than key, to one position ahead 
          of their current position */
        while (j >= 0 && arr[j] > last) 
        { 
            arr[j+1] = arr[j]; // 12, 11, 13, 5, 6
            j--; 
        } 
        arr[j+1] = last; 
    } 
     // 12, 11, 13, 5, 6
    // Driver Method 
    public static void main(String[] args) 
    { 
        int arr[] = {12, 11, 13, 5, 6}; 
 
        insertionSortRecursive(arr, arr.length); 
 
        System.out.println(Arrays.toString(arr)); 
    } 
 
    private static void print(String passage_ligne_8_n, int n) {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }
}

Et j'obtiens ce message d'erreur :

Exception in thread "main" java.lang.UnsupportedOperationException: Not supported yet.
	at insr.java.insr.print(insr.java:50)
	at insr.java.insr.insertionSortRecursive(insr.java:18)
	at insr.java.insr.main(insr.java:44)
C:\Users\Kingdel\AppData\Local\NetBeans\Cache\8.2\executor-snippets\run.xml:53: Java returned: 1
BUILD FAILED (total time: 0 seconds)

Pourtant voire apparaître plus de variables que ne le propose Netbean en mode "pas à pas" serait une source de compréhension appréciable. Peut-être tbc pourrais-tu préciser ta méthode ? Je voudrais bien comprendre ce que tu veux dire.

Merci