Quicksort - powodem jest równa weryfikacje

Question

wiele przykładów w internecie o Quicksort (w Javie) są zbliżone do tego:

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); 
} 

Rzecz jestem zaskoczony o to, dlaczego są tacy równa kontrole:

1) while (i <= j) zamiast while (i < j)

2) if (i <= j) zamiast if (i < j)

Czy są jakieś przypadki skrajne, w których ta liczba jest kluczowa? Z mojego rozumienia, gdybyśmy mieli if(i == j), wówczas zasadniczo wymienialibyśmy tę samą wartość o tej samej wartości.

Ktoś może rozwiązać to zagadnienie dla mnie?

Answer 1

Załóżmy, że stan został zastąpiony przez i < j.

Pozwala zobaczyć, co by się stało, do tablicy jak:

5,4,3,2,1 

czas pętla będzie kończyć się i = 2 i j = 2 i musielibyśmy nakładających połączeń funkcjonować quicksort i te rozmowy będą:

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

natomiast jeśli mamy ten warunek i<=j pętla by zakończyć z i = 4 i j = 1 i teraz wou Nazywa się:

, które są właściwe.

Więc w zasadzie masz rację nie ma sensu zamiana te same elementy, ale autor kodu musi pominięto go w celu uniknięcia konieczności dodawania dodatkowy warunek, że nie musisz zamienić kiedy równa j