クイックソートについての基本的質問
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の要素数と考えたのですが…。
以上、長々と書いてしまいましたが、
よろしくお願い致します。
お礼
なるほど、有り難うございました