クイックソートについての基本的質問

質問

Cのアルゴリズムを勉強中の者です。
某プログラム本に以下のソースが載っていたのですが
分からない点が１点あります。
とりあえずソースは以下の通りです。
/***********(プログラム開始)************/
/*************************************
* 昇順のクイックソート *
*************************************/
void QAscendingSort(char a[], int first, int last)
{
char temp;
int forward = first;
int backward = last - 1; /* a[last]は枢軸に充てる */

register char pivot = a[backward--];

/* 配列の要素が１個なら大小のグループ分けを終了する */
if (first >= last - 1)
return;

/* 配列の要素を枢軸を基準にして、左側に小のグループ、
* 右側に大のグループと振り分ける
*/
while (1)
{
/* 枢軸より小ならforwardを前進（インクリメント）する */
while (a[forward] < pivot)
forward++;
/* 枢軸より大ならbackwardを後退（デクリメント）する */
while (a[backward] > pivot)
backward--;

/* forwardとbackwardが交差すれば配置換えを終了 */
if (forward >= backward)
break;

/* forward要素とbackward要素を交換する */
temp = a[forward];
a[forward++] = a[backward];
a[backward--] = temp;
}

/* pivotを所定の位置に置く */
a[last - 1] = a[forward];
a[forward] = pivot;

/* 左側のグループをさらに大小のグループに分類する */
QAscendingSort(a, first, forward);

/* 右側のグループをさらに大小のグループに分類する */
QAscendingSort(a, forward + 1, last);
}
int main(void)
{
int i;

/* char型の配列を用意する */
char a[] = {'O', 'W', 'E', 'R','M', 'T', 'Z', 'Q',
'J', 'D', 'A', 'I', 'F', 'B', 'P', 'X', 'Y', 'G',
'K', 'S', 'H', 'U', 'C', 'V', 'N', 'L'};

int n = sizeof(a) / sizeof(char);

puts("<昇順にクイック\ソ\ー\ト>");
/* 配列の内容を表示 */
puts("[\ソ\ー\ト前]");
for (i = 0; i < n; i++)
printf("%c ", a[i]);
printf("\n");

/* 配列を昇順に分類する */
QAscendingSort(a, 0, n);

/* 配列の内容を表示 */
puts("[\ソ\ー\ト後]");
for (i = 0; i < n; i++)
printf("%c ", a[i]);
printf("\n");
return 0;
}
/***********(プログラムはここまで)************/
分からないのはQAscendingSort関数の
仮引数first、lastが何を意味しているかです。
取り敢えず自分ではfirstは配列aの最前列要素の添え字、
lastは配列aの要素数と考えたのですが…。

以上、長々と書いてしまいましたが、
よろしくお願い致します。

回答No.2

chie65535 · ベストアンサー

＞取り敢えず自分ではfirstは配列aの最前列要素の添え字、
＞lastは配列aの要素数と考えたのですが…。

違います。

first、lastは、文字通り「最初の要素番号」と「最後の要素番号＋１」を指定します。

＞/* 左側のグループをさらに大小のグループに分類する */
＞QAscendingSort(a, first, forward);
＞/* 右側のグループをさらに大小のグループに分類する */
＞QAscendingSort(a, forward + 1, last);
の部分は「forwardを境に、左グループと右グループを処理」してます。

最初に与えられたlast（これは「int n = sizeof(a) / sizeof(char);」の式により「最後の要素番号＋１」になる）は、最後の最後まで変化しません。

もしlastが「最後の要素番号＋１」ではなく「要素数」であるなら「先頭の要素番号を変えたなら、要素数も変えなければならない筈」です。

引数は、以下のような値が渡される筈です。
・最初の呼び出し：a,0,26
・forwardが仮に10になった場合の左グループの呼び出し：a,0,10
・forwardが仮に10になった場合の右グループの呼び出し：a,11,26

「lastが要素数」であるなら、右グループの引数は「a,11,26」ではなく「a,11,15」になる筈です。11番目から26番目までの要素数は15個ですからね。

でも、そうは動きません。

最初のlastを求める式「int n = sizeof(a) / sizeof(char)」が、「配列の要素数を求める式」として良く書く式「sizeof(配列名) / sizeof(１要素の型)」と同じ形をした式だったので「lastは要素数」だと勘違いしたのでしょう。

ですが、本当は「lastは最後の要素位置＋１」です。

お礼

有難うございました。
自分でも分からなかったところがすっきりしました。
返事が遅れて申し訳ありませんでした。

回答No.1

Tacosan

「last」という英単語は何を意味すると思いますか?
厳密にはちょっと違うんだけど....

お礼

「最後」ですよね？ってことは
配列の最後の添字ってことですか？