Java Quicksort dlaczego/gdzie zmieniają się wartości?

Question

W tej chwili uczę się języka Java w szkole, a nasz najnowszy temat to algorytmy sortowania w języku Java. Ten, który próbuję zrozumieć, to quicksort.

Aby zrozumieć, w jaki sposób algorytm sortuje liczby w tablicy, zdecydowałem się przejść przez krok mojego kodu do kroku w oknie debugera Eclipse.

Teraz był jeden krok, którego nie mogę zrozumieć, nawet po przejściu przez to, co było setkami razy.

Mój początkowy tablicy jest [10, 5, 3, 22, 11, 2]

Kiedy idę przez kod uruchamia program poprzez zamianę 10 i 2, potem 5 i 3 a następnie 2 i 2. W tym momencie wartość dla i to 1, a wartość dla j to -1.

Teraz tak jak ja to widzę, że istnieją trzy warunki

1. while(i<=j) Które zwraca false, ponieważ i = 1 i j = -1

2. if(left < j) Które zwraca false, ponieważ left = 0 i j = -1

3. if(i < right) Który również zwraca false, ponieważ i = 1 i right = 1

Ale ku mojemu zaskoczeniu, gdy program dojdzie do ostatniego wspornika tuż przed public static void display program przeskakuje z powrotem do linii 40 if(i < right) ale nagle wartości right, i, j i pivot zmieniły się odpowiednio z na 5, 2, -1 i 3.

Byłbym bardzo wdzięczny, gdyby ktoś mógł wyjaśnić, dlaczego wartości się zmieniają.

Dodałem również dwa zdjęcia, które pokazują, co widzę na moim oknem 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); 
    } 
} 

Dzięki wielkie!

Answer 1

Myślę, że Twoim problemem jest to, że nie w pełni rozumiesz rekursję. Przynajmniej tak brzmi to z twojego opisu tego pytania.

W każdym razie, próbowałem po prostu śledzić twój program, zachowując ślad wszystkich zmiennych. Nadzieję, że to pomaga:

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 

Pętla natomiast zakończyła ponieważ i<=j jest teraz false (2 > 1).

Pierwszy warunek left < j (0 < 1) jest true, więc zadzwonić quicksort ponownie rekurencyjnie: quicksort(arr, 0, 1) - co oznacza, że ​​teraz posortować tablicę [2,3] który jest już posortowane, więc nic się nie stanie:

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 

czas stan pętli to teraz false. Pierwszy warunek: left < j jest również (ponieważ 0 > -1) i drugi warunek i < right jest również fałszywy (ponieważ 1 == 1) Tak więc połączenie jest zakończone i powracasz do miejsca, w którym byłeś. Czy to było? Pierwszy warunek powyższej tabeli. Stan zmiennych i parametrów jest teraz następujący:

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

Drugi warunek jest sprawdzany (ponieważ jest to wykonywany następny wiersz). Jego wartość jest również prawdą, ponieważ warunkiem jest i < right (2 < 5). Więc teraz zrobić quicksort ponownie rekurencyjnie: quicksort(arr, 2, 5) - co oznacza, że ​​teraz posortować tablicę [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 teraz więc wyjść z pętli while.

Pierwszy warunek left < j (2 < 4) jest true, więc nazywamy quicksort(arr, 2, 4) w celu uporządkowania [5,10,11] który jest już posortowana. Pominę tę część, ponieważ w ogóle nie zmieni ona tablicy.

Po wywołaniu rekurencyjnym wracamy do miejsca, w którym się znajdowaliśmy, a teraz zostanie sprawdzony drugi warunek. i < right (5 < 5) jest false Tak więc skończyliśmy.

Oryginalne połączenie quicksort zostało zakończone, a tablica została posortowana.

Answer 2

Pierwsze zdjęcie pokazuje, że debugger znajduje się wewnątrz dwóch rekurencyjnych wywołań quicksort: quicksort jest wywoływany z głównego, a następnie na linii 38 wywołuje ponownie quicksort (jest to zasada quicksort, jest to strategia rekursywna). Więc widzisz, że jesteś w linii 40 połączenia wewnętrznego, a kiedy stamtąd wyjdziesz, wracasz do poprzedniej inwokacji quicksort (debugger pokazuje stos dwóch linii zamiast trzech w lewym górnym oknie), i powróciłeś do poprzednich wartości pivot, itd. Tablica jest przekazywana tak jak do wszystkich wywołań rekursywnych, więc jest udostępniana, ale zmienne liczb całkowitych nie są.

Myślę, że tutaj jest rekursja, która sprawia, że ​​trudno to zrozumieć, sprawdź swój stos wywołań.

Answer 3

Twoje wysiłki związane z badaniem algorytmów sortowania za pomocą instrukcji print i debuggera są godne pochwały! Ale twoja obecna implementacja Quicksorta jest raczej trudna do zrozumienia, przynajmniej początkowo, ponieważ ma zarówno iterację, jak i rekurencję (tzn. Używasz pętli i jednocześnie wywołujesz samą procedurę).

Przyjrzyjmy się raczej odmiennemu podejściu (podejście czysto rekurencyjne), aby sprawdzić, jak działa Quicksort i dlaczego działa. Konwersja tej rekursywnej procedury na iteracyjną (tak jak napisałeś) jest, na szczęście, kwestią techniki (w tym przypadku)! Proponuję, abyśmy zrobili to tutaj, ponieważ w ten sposób moglibyśmy lepiej kontrolować złożoność. Powtarzam, dlatego robię to, aby lepiej zrozumieć, co się dzieje.

Kiedy Sir Tony Hoare zaproponowany algorytm i udowodnił jego poprawności, to było coś takiego:

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

To jest to! Czy nie jest piękne? No cóż, tak jest. Wszystko, co musisz zrobić, to:

• Partycja podana tablica. W moich oczach partycjonowanie jest elegancką procedurą, która dobrze rozwiązuje trudny problem. Problem jest prosty: Biorąc pod uwagę tablicę liczb, przestawia tablicę tak, że jest w niej liczba, wszystkie liczby po lewej stronie są mniejsze lub równe, a wszystkie liczby po prawej stronie są większe niższy lub równy - zwróć wskaźnik takiego elementu w tablicy. Zachęcam do samodzielnego rozwiązania tego problemu. Obie procedury (Lomuto i Hoare) podane na Wikipedii działają dobrze.
• Po upewnieniu się, że podział działa zgodnie z oczekiwaniami, to rekurencyjnie sort dwie partycje stosując tę ​​samą procedurę qsort (kolejność wywołań rekurencyjnych robi nie materia) i gotowe!

starałem się wdrożyć procedurą partition sobie:

/** 
    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; 
    } 

Teraz jeszcze nie udowodnił poprawności tej procedury, ale możemy to zrobić oddzielnie. Możesz nawet ponownie wdrożyć Lomuto procedure i przekonać się, że działa w sposób satysfakcjonujący.

I to wszystko. Jeśli chcesz teraz debugować to za pomocą debuggera, jesteś bardziej niż przygotowany do tego. Oto entire implementation.

Teraz kwestia przekształcania tej procedury rekurencyjnej do iteracyjnego jeden jest bardzo ciekawy i ten dokument: (wtyczka bezwstydny: Napisałem ją) http://bit.ly/recurse-iterate powinno dać pewne wskazówki. Rzeczywistą konwersję powyższej procedury Quicksort na iteracyjną należy pozostawić ćwiczącemu :-).