Java Quicksort Почему/где значения меняются?

Question

Я изучаю Java в школе прямо сейчас, и наша последняя тема - алгоритмы сортировки на Java. Тот, который я пытаюсь понять, быстро сортируется.

Чтобы понять, как этот алгоритм сортирует числа в массиве, я решил пройти мой шаг кода для шага в окне отладчика Eclipse.

Теперь был один шаг, который я не могу понять, даже пройдя через него, что было похоже на сотни раз.

Мой первоначальный массив [10, 5, 3, 22, 11, 2]

Когда я иду через код запускает программу путем замены 10 и 2, затем 5 и 3, а затем 2 и 2. В этот момент значение для i составляет 1, а значение для j - -1.

Теперь, как я вижу, что есть три условия

1. while(i<=j) Который возвращает false, потому что i = 1 и j = -1

2. if(left < j) Который возвращает false, потому что left = 0 и j = -1

3. if(i < right) Который также возвращает false, потому что i = 1 и right = 1

Но к моему удивлению, когда программа дойдет до последней скобки перед public static void display программа переходит обратно на линию 40 if(i < right) но вдруг значений right, i, j и pivot были изменены с 5, 2, -1, и 3 соответственно.

Я был бы очень благодарен, если бы кто-нибудь мог объяснить, почему значения меняются.

Я также добавил две фотографии, которые показывают, что я вижу на моем окне 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); 
    } 
} 

Спасибо большое!

Answer 1

Я думаю, ваша проблема в том, что вы не полностью понимаете рекурсию. По крайней мере, это то, что кажется по вашему описанию вопроса.

В любом случае, я попытался просто следовать вашей программе, сохранив следы всех переменных. Надеюсь, что это помогает:

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 

Петля в то время как закончил, потому что i<=j теперь false (2 > 1).

Первое условие left < j (0 < 1) является true, так что вы звоните quicksort снова рекурсивно: quicksort(arr, 0, 1) - это значит, теперь сортирует массив [2,3], который уже отсортирован, так что ничего не случится:

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 

это время Условие цикла теперь false. Первым условием left < j является false (так как 0 > -1), а второе условие i < right также неверно (потому что 1 == 1) Итак, этот вызов завершен, и вы вернетесь туда, где вы были. Это было так? Первое условие таблицы выше. Состояние переменных и параметров в настоящее время:

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

Второе условие проверено (так как выполняется следующая строка). Его значение также верно, так как условие равно i < right (2 < 5). Так что теперь делать quicksort снова рекурсивно: quicksort(arr, 2, 5) - это значит, теперь сортирует массив [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 теперь так мы выходим из цикла.

Первое условие left < j (2 < 4) является true, поэтому мы называем quicksort(arr, 2, 4) для сортировки [5,10,11], который уже отсортирован. Я пропущу эту часть, поскольку она вообще не изменяет массив.

Когда рекурсивный вызов завершен, мы вернемся туда, где мы были, и теперь будет проверено второе условие. i < right (5 < 5) - false Итак, мы закончили.

Окончание вызова quicksort завершено, и массив отсортирован.

Answer 2

Первый снимок, который вы показываете отладчиком, находится внутри двух рекурсивных вызовов quicksort: quicksort вызывается из main, а затем в строке 38 снова вызывается quicksort (это принцип быстрой сортировки, это рекурсивная стратегия). Итак, вы видите, что вы находитесь в строке 40 внутреннего вызова, а затем, когда вы переходите оттуда, вы возвращаетесь к предыдущему вызову quicksort (отладчик показывает вам стек из двух строк вместо трех в верхнем левом окне), и вы вернулись к предыдущим значениям pivot и т. д. Массив передается как и для всех рекурсивных вызовов, поэтому он является общим, но целые переменные не являются.

Я думаю, что здесь рекурсия затрудняет понимание, проверьте стек вызовов.

Answer 3

Ваши усилия по изучению алгоритмов сортировки с использованием операторов печати и отладчика заслуживают одобрения! Но ваша текущая реализация Quicksort довольно сложно понять, по крайней мере изначально, потому что у нее есть итерация и рекурсия (например, вы используете циклы и в то же время у вас есть процедура quicksort).

Давайте рассмотрим совсем другой подход (чисто рекурсивный подход), чтобы увидеть, как работает Quicksort и почему он работает. Преобразование этой рекурсивной процедуры в итеративную (как это было написано вами), к счастью, является вопросом техники (в данном случае)! Я предлагаю, чтобы мы сделали это здесь, потому что таким образом мы могли бы лучше контролировать сложность. Опять же, причина, по которой я делаю это, - лучше понять, что происходит.

Когда сэр Тони Хоара предложил алгоритм и доказал свою правоту, это было что-то вроде этого:

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

Вот оно! Не красиво? Ну, это так. Все что вы делаете:

• Раздел данный массив. На мой взгляд, разбиение является элегантной процедурой для решения сложной проблемы. Проблема проста: учитывая массив чисел, перегруппируйте массив таким образом, чтобы в нем было число, все числа слева от которого меньше или равны ему, а все номера справа от них больше чем или равно ему - вернуть индекс такого элемента в массив. Я настоятельно рекомендую вам решить эту проблему самостоятельно. Обе процедуры (Ломуто и Хоар), данные в Википедии, хорошо работают.
• После того, как вы уверены, что ваше секционирование работает, как ожидалось, вы рекурсивна сортировать два раздела с использованием тех же qsort процедуру (порядок рекурсивных вызовов делает не вещества) и вы сделали!

Я пыталась реализовать partition процедуру себя:

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

Теперь, я еще не доказал правильность этой процедуры, но мы можем сделать это отдельно. Вы даже можете переопределить Lomuto procedure и увидеть, что он работает на ваше удовлетворение.

И все. Если вы хотите отлаживать это с помощью отладчика, вы более чем можете это сделать. Вот entire implementation.

Теперь вопрос о преобразовании этой рекурсивной процедуры повторяющийся очень интересно, и этот документ: (бесстыдный штепсель: Я написал) http://bit.ly/recurse-iterate должен дать вам некоторые подсказки. Фактическое преобразование вышеприведенной процедуры Quicksort в итеративную версию остается в виде упражнения для читателя :-).