Répondre à la discussion
Affichage des résultats 1 à 2 sur 2

algorithme par insertion récursif



  1. #1
    candelaria

    algorithme par insertion récursif

    Bonjour,
    J'etudie algorithme par insertion recursif. Et un mystère demeure insoluble dans ce code :

    Code:
    // Recursive Java program for insertion sort
    
    import java.util.Arrays;
    
    public class GFG
    {
    // 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));
    }
    }

    lorsque le code appelle cinq fois de la méthode " insertionSortRecursive( arr, n-1 ); " il semble faire que le tableau va être évalué de gauche à droite.

    Alors que le code " int last = arr[n-1];" et " int j = n-2; " (linge 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 sont en sens contraire.

    Illusion d'esprit ? Ou tout le monde va dans e même sens ? Mais comment cela s'explique ?

    Merci,

    Intelego.

    -----


  2. #2
    Bounoume

    Re : algorithme par insertion récursif

    pas encore de réponse? C'est que c'est l'hiver, et que tout est gelé? Alors voici une réponse par défaut
    quand tu dis 'début' et 'fin' du tableau...... c'est ambigu.....
    Disons que 'début' ça veut dire indice Zéro, et Fin c'est le + grand cad tab[4] (je connais pas python, mais je suppose que les indices commencent à zéro, comme en C.)

    Cela dit, dans ta récursion, le programme va commencer à exécuter
    insertionSortRecursive(int arr[], int n=4)
    {........
    comme le code rencontre tout de suite insertionSortRecursive( arr, n-1)

    ça fait x=4 -1 ...... ce qui a pour valeur "3" !!!!
    donc la fonction appelée est
    insertionSortRecursive(int arr[], int n=3)
    Ni l'appel initial, d'argument n=4, ni cet appel d'argument n=3 ne calculent encore quoi que ce soit.

    en revanche récursivement on appelle ensuite
    insertionSortRecursive(int arr[], int n=2)
    puis
    insertionSortRecursive(int arr[], int n=1)
    puis
    insertionSortRecursive(int arr[], int n=0) .... c'est la fonction d'argument n=Zéro.......

    Là il se passe quelque chose: le return, puisqu en tout début la condition if est satisfaite:
    if (n <= 1)
    return;
    donc retour du dernier appel..... MAIS........

    ce que tu n'as pas probablement pas intégré, c'est que dans des appels récursifs le programme EMPILE les appels de fonction:

    lorsque le 'return' s'exécute, la dernière fonction empilée (celle à argument Zéro) se termine........

    et alors la fonction précédemment empilée
    (celle d'argument n=1)........ reprend son exécution aprés le retour d'appel avorté à (celle à argument Zéro) !

    la fonction d'argument n=1 traite donc alors les 2 premières valeurs (indices 0 et 1)..... donc last=arr[1] et donc en fin de fonction on est sûr que: arr[1]>arr[0]
    la fonction this se termine.... et alors est dépilée ce qui reste à exécuter de la fonction à argument n=2

    la fonction à argument 2 reprend, insère last=arr[2] à sa bonne place par rapport à [arr0], [arr1] (déjà dans le bon ordre) en décalant si besoin les valeurs en pos 0 et éventuellement 1 ...
    puis c'est la fonction d'argument 3 fraîchement dépilée qui va placer la valeur last=arr[2] à sa bonne place, en décalant si besoin les premières places


    etc...

    le principe est effectivement un aller-retour dans l'exécution de la récursion, et au retour sont progressivement remis en ordre les contenus, en commençant par le début du tableau <=> les poids faibles <=> la 'gauche' du tableau, si tu as choisi d'écrire les valeurs par indices croissants.....
    l
    le bruit tue l'information......

Discussions similaires

  1. complexité d'un algorithme recursif
    Par bmce dans le forum Programmation et langages, Algorithmique
    Réponses: 5
    Dernier message: 08/12/2016, 06h25
  2. dossier appel récursif
    Par moijdikssékool dans le forum Logiciel - Software - Open Source
    Réponses: 6
    Dernier message: 27/02/2014, 18h36
  3. comprendre un filtre récursif
    Par saraviva dans le forum Électronique
    Réponses: 0
    Dernier message: 27/05/2012, 21h28
  4. Algorithme d'insertion à coût minimum
    Par celine2 dans le forum Programmation et langages, Algorithmique
    Réponses: 5
    Dernier message: 20/04/2011, 15h34
  5. [UNIX] Path recursif
    Par Tonton Nano dans le forum Logiciel - Software - Open Source
    Réponses: 2
    Dernier message: 23/10/2007, 09h31