algorithme par insertion récursif

[invite5f6edd59]

Bonjour,
J'etudie algorithme par insertion recursif. Et un mystère demeure insoluble dans ce 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.
-----

[Bounoume]

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