Recursion in the quick sort algorithm (Java)

Question

There is an algorithm itself, but the question is this: when the first half of the array is sorted (the left side, the one that is smaller than the pivot), it is supposed to leave the method because both conditions do not work

if (left < j) qs(items, left, j); if (i < right) qs(items, i, right);

but he jumps back into the second if and somehow gives the value i = 3 and starts sorting the second half. The question is how did he understand it? Or is it a recursive call feature?

Here is the code itself :

class Quicksort {

 // Организовать вызов фактического метода быстрой сортировки static void qsort(int[] items) { qs(items, 0, items.length - 1); } // Рекурсивная версия метода быстрой сортировки символов private static void qs(int[] items, int left, int right) { int i = left; int j = right; int pivot, TEMP; pivot = items[(left + right) / 2]; do { while ((items[i] < pivot) && (i < right)) i++; while ((pivot < items[j] && (j > left))) j--; if (i <= j) { TEMP = items[i]; items[i] = items[j]; items[j] = TEMP; i++; j--; } } while (i <= j); if (left < j) qs(items, left, j); if (i < right) qs(items, i, right); }

}

public class QSDemo {

 public static void main(String[] args) { int[] a = {17, -24, 20, -15, -21, -3, 13}; System.out.println("Исходный массив: "); for (int i = 0; i < a.length; i++) System.out.print(a[i] + " "); System.out.println(); // Отсоритровать массив Quicksort.qsort(a); System.out.println("Отсортированный массив: "); for (int i = 0; i < a.length; i++) System.out.print(a[i] + " "); }

}

Accepted Answer · 2018-04-09T15:45:41

Why don't both conditions work?
This can happen only with a small range length - 1 or 2

Speculatively for the given array and the indicated choice of the separator, the process will go like this:

  17, -24, 20, -15, -21, -3, 13 после первого partition -21, -24, -15, 20, 17, -3, 13

Now both subbands 0..2 and 3..6 are processed. First, the first if makes a recursive call on subrange 0..2, the first half is sorted. Only after that the exit to the first recursion level occurs, where still left = 0, right = 6, and the second is triggered if The sequence of recursive calls will be like this (left, right values, recursion level (depth)):

 0 6 1 0 2 2 1 2 3 3 6 2 3 4 3 5 6 3

How does he assign i a value of 3 and start sorting further ????
when the first part of the pivot is sorted, it does not go into one if not into the second if, but goes down to the end of the method and must come out of it, but this does not happen!
it eventually jumps into the second if and gives the value i = 3!
At what level of recursion, at what left, right does it occur?
At this moment, he does not pass a single condition and gets up at the end of the curly bracket and when you press to go further, he eventually jumps on the second condition with parameters i = 3, right = 6, left = 0. I understand how this algorithm works , but I can not understand how the computer received these numbers

Recursion in the quick sort algorithm (Java)

1 answer 1

More articles: