質問: partition(array, left, right); quick_sort(array, left, pivot-1); //pivotを境に再帰的にクイックソート quick_sort(array, pivot+1, right); } } ``` ``` 実行結果: Before sort: 3 2 6 1 5 4 After sort: 1 2 3 4 5 6 ``` **1**クイックソート関数の if (left < right) という部分の意図がわかりません。 なぜ、このような条件をつけているのでしょうか?なくてもいいような気がします。 **2**クイックソート関数の quick_sort(array, left, pivot-1); quick_sort(array, pivot+1, right); なぜ2回も再帰を行なっているのでしょうか? それと、引数が2つとも違うのはなぜなんでしょうか?
回答: クイックソートは、言語ではなくて、アルゴリズムですから、文法というのは変です。 int array[SIZE] = {3, 2, 6, 1, 5, 4}; の状態で quick_sort(array, 0, 5) を呼び出します。 left = 0, right = 5 です。left < right ですから、 pivot = partition(array, left, right) を呼び出します。 戻ってきたとき、 array = { 2, 1, 3, 6, 5, 4 }, pivot = 2 になっています。 array[pivot] = array[2] = 3 で、 { 2, 1 } は 3 より小さい。{ 6, 5, 4 } は 3 より大きい。 { 2, 1 } をソートするため quick_sort(array, left, pivot-1) を呼び出し { 6, 5, 4 } をソートするため quick_sort(array, pivot+1, right) を呼び出します。 これが 2回も再帰を行ない、引数が2つとも違う理由です。 これを繰り返すと、ソートする部分の長さがだんだん小さくなって 0 か 1 になります。 left < right だとソートする array の要素が 2個以上あるのでソートが必要ですが、 そうでないとソートする必要がありません。 そのため if (left < right) という条件が付いているのです。