C言語 クイックソートの文法の意図が分からない

Question

#include <stdio.h>
#define SIZE    6


void quick_sort(int[], int, int);

int main()
{
    int array[SIZE] = {3, 2, 6, 1, 5, 4};
    int i;
    
    printf("Before sort: ");
    for (i = 0; i < SIZE; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    
    quick_sort(array, 0, 5);
    
    printf("After sort: ");
    for (i = 0; i < SIZE; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

//値を入れ替える関数
void swap(int *x, int *y) {
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

/***
 * pivotを決め、
 * 全データをpivotを境目に振り分け、
 * pivotの添え字を返す
 ***/
int partition(int array[], int left, int right) {
    int i, j, pivot;
    
    i = left;
    j = right + 1;
    //先頭要素をpivotとする
    pivot = left;
    
    do {
        do {i++; } while (array[pivot] > array[i]);
        do {j--; } while (array[pivot] < array[j]);
        //pivotより小さいものを左へ、大きいものを右へ
        if (i < j) {
            swap(&array[i], &array[j]);
        }
    } while (i < j);
    swap(&array[pivot], &array[j]);
    //pivotを更新
    return j;
}

////クイックソート
void quick_sort(int array[], int left, int right) {
    int pivot;
    if (left < right) {
        pivot = 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

①クイックソート関数の
if (left < right)　という部分の意図がわかりません。
なぜ、このような条件をつけているのでしょうか？なくてもいいような気がします。

②クイックソート関数の
quick_sort(array, left, pivot-1);
quick_sort(array, pivot+1, right);
なぜ２回も再帰を行なっているのでしょうか？
それと、引数が２つとも違うのはなぜなんでしょうか？

Comments

[Zuishin]

前半と後半をソートすればすべてソートできるというのがクイックソートのアルゴリズムの基本です。
だから半分に分けて二回ソートします。

left < right は継続条件です。
left >= right になったら終了です。

[otn]

まずは、「クイックソートとは何なのか？」を理解しましょう。
https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88

Answer 1

クイックソートは、言語ではなくて、アルゴリズムですから、文法というのは変です。

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) という条件が付いているのです。

Comments

[GIOGIO]

ありがとうございます。ようやく理解できました！