Java Quicksort perché/dove cambiano i valori?

Question

Sto imparando Java a scuola in questo momento e il nostro ultimo argomento sono algoritmi di ordinamento in Java. Quello che sto cercando di capire è quicksort.

Per capire come quell'algoritmo ordina i numeri in un array ho deciso di passare attraverso il mio passo di codice per il passaggio nella finestra del debugger di Eclipse.

Ora c'era un passo che non riesco a comprendere nemmeno dopo averlo attraversato, cosa che mi è sembrato centinaia di volte.

La mia matrice iniziale è [10, 5, 3, 22, 11, 2]

Quando vado attraverso il codice del programma inizia scambiando 10 e 2, poi 5 e 3 e poi 2 e 2. A quel punto il valore per i è 1 e il valore per j è -1.

Ora il mio modo di vedere è che ci sono tre condizioni

1. while(i<=j) che restituisce false, perché i = 1 e j = -1

2. if(left < j) che restituisce false, perché left = 0 e j = -1

3. if(i < right) Che anche restituisce false, perché i = 1 e right = 1

Ma con mia sorpresa quando il programma ottiene l'ultimo staffa a destra prima public static void display il programma salta di nuovo alla riga 40 if(i < right) ma improvvisamente i valori per right, i, j e pivot sono passati da 5, 2, -1 e 3 rispettivamente.

Sarei molto grato se qualcuno potrebbe spiegare perché i valori vengono modificati.

Ho anche aggiunto due foto che mostrano quello che vedo sulla mia finestra Eclipse step I don't understand

public class QSort { 

    public static void quickSort(int[] arr, int left, int right){ 
     int i = left; 
     int j = right; 
     int temp; 
     int pivot = arr[(left+right)/2]; 
     System.out.println("\n\nleft = " + left + "\tright = " + right); 
     System.out.println("Pivot is: " + pivot + "(" + (left+right)/2 + ")"); 
     while(i <= j){ 
      while(arr[i] < pivot){ 
       System.out.println("i is: " + arr[i] + "(" + i + ")"); 
       i++; 
       System.out.println("i is: " + arr[i] + "(" + i + ")"); 
      } 
      while(arr[j] > pivot){ 
       System.out.println("j is: "+ arr[j] + "(" + j + ")"); 
       j--; 
       System.out.println("j is: "+ arr[j] + "(" + j + ")"); 
      } 
      if(i <= j){ 
       System.out.println("i is: " + arr[i] + "(" + i + ")"); 
       System.out.println("j is: "+ arr[j] + "(" + j + ")"); 
       System.out.println("Swapped " + arr[i] + "(" + i + ")"+ " with " + arr[j] + "(" + j + ")"); 
       temp = arr[i]; 
       arr[i] = arr[j]; 
       arr[j] = temp; 
       i++; 
       j--; 
       System.out.println("i is: (" + i + ")"); 
       System.out.println("j is: (" + j + ")"); 
       System.out.println("Pivot is: " + pivot + "(" + (left+right)/2 + ")"); 
      } 
     } 
     if(left < j){ 
      System.out.println("j is: (" + j + ")"); 
      quickSort(arr, left, j); 
     } 
     if(i < right){ 
      System.out.println("i is: (" + i + ")"); 
      quickSort(arr, i, right); 
     } 
    } 

    public static void display(int[] arr){ 
     if(arr.length > 0){ 
      System.out.print(arr[0]); 
     } 
     for(int i = 1; i < arr.length; i++){ 
      System.out.print(", " + arr[i]); 
     } 
    } 

    public static void main(String[] args) { 
     int[] data = new int[]{10,5,3,22,11,2}; 
     System.out.println("Before: "); 
     display(data); 
     quickSort(data, 0, data.length-1); 
     System.out.println("\nAfter: "); 
     display(data); 
    } 
} 

Grazie mille!

Answer 1

Penso che il tuo problema sia che non capisci completamente la ricorsione. Almeno questo è quello che sembra dalla tua descrizione della domanda.

In ogni caso, ho provato a seguire semplicemente il programma tenendo traccia di tutte le variabili. Spero che questo aiuta:

arr     left  right  i   j  pivot 
----------------- ------- -------- ------- ----- ---------- 
[10,5,3,22,11,2] 0   5   
              0   5  arr[2] = 3 
[2,5,3,22,11,10]       1   4 
                3 
                2 
[2,3,5,22,11,10]       2   1 

Il ciclo while è terminata perché i<=j è ora false (2 > 1).

La prima condizione left < j (0 < 1) è true, così si chiama quicksort di nuovo in modo ricorsivo: quicksort(arr, 0, 1) - il che significa che ora ordinare l'array [2,3] che è già ordinato, in modo da non accadrà nulla:

arr     left  right  i   j  pivot 
----------------- ------- -------- ------- ----- ---------- 
[2,3,5,22,11,10] 0   1 
              0   1  arr[0] = 2 
                0 
[2,3,5,22,11,10]       1   -1 

La mentre la condizione del loop è ora false. La prima condizione left < j è(perché 0 > -1) e la seconda condizione i < right è anch'essa falsa (perché 1 == 1) Quindi questa chiamata è terminata e si ritorna a dove si era. Eri quello? La prima condizione della tabella sopra. Lo stato delle variabili e dei parametri è ora:

arr     left  right  i   j  pivot 
----------------- ------- -------- ------- ----- ---------- 
[10,5,3,22,11,2] 0   5   2   1  3 

La seconda condizione è verificata (come è la linea successiva esecuzione). Il suo valore è anche vero poiché la condizione è i < right (2 < 5). Quindi ora fai quicksort di nuovo in modo ricorsivo: quicksort(arr, 2, 5) - il che significa che ora ordinare l'array [3,22,11,10]:

arr     left  right  i   j  pivot 
----------------- ------- -------- ------- ----- ---------- 
[2,3,5,22,11,10]   2   5   
              2   5  arr[3] = 22 
              3 
[2,3,5,10,11,22]       4   4 
              5 

i > j ora così si esce dal ciclo while.

La prima condizione left < j (2 < 4) è true, così noi chiamiamo quicksort(arr, 2, 4) per ordinare [5,10,11] che è già ordinato. Salterò questa parte in quanto non cambia affatto la matrice.

Quando la chiamata ricorsiva è terminata, torniamo a dove eravamo e ora verrà controllata la seconda condizione. i < right (5 < 5) è false E così abbiamo finito.

La chiamata originale quicksort è terminata e l'array è ordinato.

Answer 2

La prima immagine visualizzata mostra che il debugger si trova all'interno di due invocazioni ricorsive di quicksort: quicksort viene chiamato da main e quindi sulla riga 38 richiama nuovamente quicksort (questo è il principio di quicksort, è una strategia ricorsiva). Quindi vedi che sei sulla linea 40 della chiamata interna, poi quando passi da lì, torni alla precedente chiamata di quicksort (il debugger ti mostra una pila di due linee invece di tre nella finestra in alto a sinistra), e si torna ai valori precedenti di pivot, ecc. L'array viene passato come è a tutte le chiamate ricorsive, quindi è condiviso, ma le variabili intere non lo sono.

Penso che qui sia la ricorsione a rendere difficile la comprensione, controllare lo stack delle chiamate.

Answer 3

I vostri sforzi di studiare un algoritmo di ordinamento utilizzando le istruzioni di stampa e un debugger sono encomiabili! Ma la tua attuale implementazione di Quicksort è piuttosto difficile da comprendere, almeno inizialmente, perché ha avuto sia iterazioni che ricorsioni (cioè tu usi i loop e, allo stesso tempo, hai una procedura da chiamare quicksort).

Facciamo un approccio piuttosto diverso (approccio puramente ricorsivo) per vedere come funziona Quicksort e perché funziona. Convertire questa procedura ricorsiva in una iterativa (un po 'come hai scritto tu) è, fortunatamente, una questione di tecnica (in questo caso)! Propongo di farlo qui perché in questo modo potremmo controllare meglio la complessità. Ancora una volta, la ragione per cui sto facendo questo è capire meglio cosa sta succedendo.

Quando Sir Tony Hoare ha proposto l'algoritmo e ha dimostrato la sua correttezza, era qualcosa di simile:

public static void qsort(int[] ints, int fi, int li) {       
    /* the recursive procedure */             
    if (fi < li) {                 
     int p = partition(ints, fi, li); // key routine -- see below           
     qsort(ints, fi, p - 1);              
     qsort(ints, p + 1, li);              
    }                    
    } 

Questo è tutto! Non è bello? Bene, lo è. Tutto ciò che fai è:

• partizione la matrice data. Ai miei occhi, partizionare è una procedura elegante per risolvere bene un problema difficile. Il problema è semplice: data una serie di numeri, riorganizza la matrice in modo tale che ci sia un numero in essa, tutti i numeri a sinistra dei quali sono più piccoli o uguali ad esso e tutti i numeri a destra dei quali sono più grandi o uguale a esso - restituisce l'indice di tale elemento nell'array. Vi esorto a cercare di risolvere questo problema da soli. Entrambe le procedure (Lomuto e Hoare) fornite su Wikipedia funzionano bene.
• Una volta che siete sicuri che il vostro partizionamento funziona come previsto, è ricorsivamente specie le due partizioni utilizzando la stessa procedura di qsort (l'ordine delle chiamate ricorsive non non materia) e si è fatto!

ho cercato di applicare la procedura partition me stesso:

/** 
    Implements partitioning of array a from a[p] to a[r], leaves all the other elements of the array intact. 
    @param a the given int array 
    @param p int first index of the part of array to be partitioned 
    @param r int the second index of the part of array to be partitioned 
*/ 
    public static int partition(int[] a, int p, int r) { 
    //this is something I have written 
    int pivot = a[p]; 
    int i = p + 1; 
    int j = i - 1; 
    while (i <= r) { 
     if (a[i] < pivot) { 
     a[j] = a[i]; 
     a[i] = a[j+1]; 
     j++; 
     } 
     i++; 
    } 
    a[j] = pivot; 
    return j; 
    } 

    private static void swap(int[] ints, int i1, int i2) { 
    int tmp = ints[i2]; 
    ints[i2] = ints[i1]; 
    ints[i1] = tmp; 
    } 

Ora, non ho ancora dimostrato l'esattezza di questa procedura, ma possiamo farlo separatamente. Puoi anche reimplementare lo Lomuto procedure e vedere che funziona in modo soddisfacente.

E questo è tutto. Se ora vuoi eseguire il debug di questo con un debugger, sei più che equipaggiato per farlo. Ecco lo entire implementation.

Ora, la domanda di conversione di questa procedura ricorsiva a un iterativo è molto interessante e questo documento: (spudorato: l'ho scritto) http://bit.ly/recurse-iterate dovrebbe darvi qualche indizio. La conversione effettiva della precedente procedura Quicksort a una iterativa viene lasciata come esercizio al lettore :-).