Как рекурсия выходит из первого рекурсивного быстрого вызова сортировки?

Question

Что сигнализирует программе сказать: «Хорошо, первый рекурсивный вызов quickSort завершен, перейдите ко второму рекурсивному вызову»?

int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high]; // pivot 
    int i = (low - 1); // Index of smaller element 

    for (int j = low; j <= high- 1; j++) 
    { 
     if (arr[j] <= pivot) 
     { 
      i++; // increment index of smaller element 
      swap(&arr[i], &arr[j]); 
     } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 

void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) 
    { 
     int pi = partition(arr, low, high); 
     quickSort(arr, low, pi - 1); 
     quickSort(arr, pi + 1, high); 
    } 
} 

Answer 1

Ваши актуальные вопросы коренятся в Recursion Stack.

Давайте сначала поймем Recursion, который в основном представляет собой метод, который продолжает называть себя все более мелким случаем и каждый раз повторяет ту же нерекурсивную процедуру, пока не достигнет базового случая, при котором останавливается.

В случае QuickSort базовым регистром рекурсии являются списки нулевого нуля или единицы, которые никогда не нужно сортировать. Если это не так, массив не предназначен для сортировки. Именно поэтому мы снова вызываем метод QuickSort дважды в массивах меньших размеров.

Мы рекурсируем на стороне массива, содержащего все элементы от A[0] to A[i - 2], и сторону массива, содержащую элементы A[i] to A[A.length - 1].

Почему мы не учитываем A[i - 1]? Простой - он уже в правильном месте.