Quicksort - motivo è uguale a controlli

Question

Molti esempi sul web su Quicksort (in Java) sono vicini a questo:

private void quicksort(int low, int high) { 
    int i = low, j = high; 
    int pivot = numbers[low + (high-low)/2]; 

    while (i <= j) { 

     while (numbers[i] < pivot) { 
     i++; 
     } 

     while (numbers[j] > pivot) { 
     j--; 
     } 

     if (i <= j) { 
     exchange(i, j); 
     i++; 
     j--; 
     } 
    } 

    if (low < j) 
     quicksort(low, j); 
    if (i < high) 
     quicksort(i, high); 
} 

La cosa di cui sono perplesso circa è il motivo per cui ci sono quelli uguale controlli:

1) while (i <= j) anziché while (i < j)

2) if (i <= j) anziché if (i < j)

Ci sono casi limite in cui questo è fondamentale? Dalla mia comprensione se avessimo if(i == j), allora fondamentalmente scambieresti lo stesso valore con lo stesso valore.

Chiunque può risolvere questo puzzle per me?

Answer 1

Supponiamo che la condizione sia sostituita da i < j.

Vediamo cosa succederebbe per un array come:

5,4,3,2,1 

Il ciclo while si termina con i = 2 e j = 2 e avremmo sovrapposte chiamate operato Quicksort e queste chiamate sarebbe:

quicksort(0,2) and quicksort(2,4) 

mentre se noi abbiamo questa condizione i<=j il ciclo sarebbe terminare con i = 4 e j = 1 e ora abbiamo wou Ho chiamate come:

quicksort(0,1) and quicksort(3,4) 

quali sono le chiamate giuste.

Quindi, in pratica hai ragione non v'è alcun punto della sostituzione degli stessi elementi, ma l'autore del codice deve avere omesso per evitare la necessità di aggiungere una condizione supplementare che non avete bisogno di scambiare quando è uguale a j