Algorithme d'insertion récursif

Version imprimable

Bonjour,

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

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
 
// 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.

08/12/2018, 21h18
AbsoluteLogic

Salut,

Citation:

Envoyé par Intelego

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.
08/12/2018, 23h48
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.
09/12/2018, 23h09
AbsoluteLogic

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

Citation:

Envoyé par Intelego

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.

Citation:

Envoyé par Intelego

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.

Citation:

Envoyé par Intelego

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.
10/12/2018, 00h03
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.

Salut,

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

Code:

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:

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

10/12/2018, 00h58
Intelego

Merci AbsoluteLogic,

Tes indications m'aide à mieux comprendre.

Le compilateur Netbean montre que très peux de variables et encore moins qu'il y a cinq méthodes qui sont en attentes dans la machine.

Quand a la mention" résolu" : je n'arrive pas à l'enlever en fait !

Merci bien.
10/12/2018, 10h23
tbc92

je propose print ( ) avec 2 paramètres... je ne connais pas la syntaxe précise ; il faut peut-être faire print ( "Passage ici " || n ) ... à toi de regarder la doc de la fonction print.

Et dans ce que je disais, il faut mettre 2 textes différents selon que tu es AVANT l'appel à la fonction récursive ou APRES.

salut

Code:

1
2
3
 
   String stringvalue = obj.toString(n); 
   System.out.println("Passage ici ... " +stringvalue);