最初の再帰的なクイックソート呼び出しから再帰がどのように壊れますか？

Question

「最初の再帰的なquickSort呼び出しが完了しました; 2番目の再帰的な呼び出しに進む」と言う信号は何ですか？

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に由来しています。

最初に理解してみましょう。これは、基本的にはますます小規模なケースで自分自身を呼び出すことを保つメソッドであり、ベースケースに達するまで毎回同じ非再帰的プロシージャを繰り返します。

QuickSortの場合、再帰の基本ケースはサイズ0または1のリストであり、決してソートする必要はありません。そうでない場合は、配列はソートされません。そのため、小さいサイズの配列に対してQuickSortメソッドを2回呼びます。

A[0] to A[i - 2]のすべての要素と、A[i] to A[A.length - 1]という要素を含む配列の辺を含む配列の側に繰り返し表示されます。

A[i - 1]はなぜ除外しますか？シンプル - すでに正しい場所にあります。