[JAVA] Insertion sort che inizia dalla fine

[noipo]

Ciao a tutti, volevo scrivere un metodo insertion sort che però iniziasse ad analizzare gli elementi dal fondo invece che dall'inizio.. C'ho provato ma non ci riesco, o mi da out of bound oppure non me lo ordina.. Ho provato a simulare la cosa a mano ma mi incasino..

L'insertion sort standard è questo

	public static void insertionSort(int[] a) {
		int n = a.length;
		for(int i = 1; i < n; i++) {
			int x = a[i];
			int j = i;
			while(j > 0 && x < a[j-1]) {
				a[j] = a[j-1];
				j--;
			}
			a[j] = x;
		}
	}

Quello che ho scritto io e che non va è:

	public static void insertionSortFine(int[] a) {
		int n = a.length - 1;
		for(int i = n; i >= 0; i--) {
			int x = a[i];
			int j = i;
			while(j < 0 && x > a[j-1]) {
				a[j] = a[j-1];
				j++;
			}
			a[j] = x;
		}
	}

Dove sbaglio?

[claudio862]

Il ciclo for parte con i = n, poi accedi all'indice i dell'array, che è oltre la fine (da 0 a n-1). Il while invece è proprio sbagliato, se j < 0 a[j] e a[j-1] non sono indici validi.

Nell'insertion sort standard il ciclo for va da 1 a n-1 (dal secondo elemento all'ultimo), quindi in quello inverso deve andare da n-2 a 0 (dal penultimo elemento al primo).
Il while dice "dalla posizione corrente, scorri fino all'inizio finché non trovi un numero maggiore di x". Quindi va da j = i fino a j = 0, o si ferma prima se x < a[j-1].
L'inverso è "dalla posizione corrente, scorri fino alla fine finché non trovi un numero minore di x". Quindi va da j = i fino a j = n-2, o si ferma prima se x > a[j+1]. Nota che è j + 1, non j - 1, perché controlli l'elemento successivo nella direzione in cui stai scorrendo l'array (verso l'inizio nell'insertion sort standard, verso la fine in quello inverso).

for (int i = n-2; i >= 0; --i) {
    int x = a[i];
    int j = i;
    while (j < n-1 && x > a[j+1]) {
        a[j] = a[j+1];
        j++;
    }
    a[j] = x;
}

[noipo]

In effetti era facile.. Grazie mille