Cのアルゴリズムを勉強中の者です。
某プログラム本に以下のソースが載っていたのですが
分からない点が1点あります。
とりあえずソースは以下の通りです。
/***********(プログラム開始)************/
/*************************************
* 昇順のクイックソート *
*************************************/
void QAscendingSort(char a[], int first, int last)
{
char temp;
int forward = first;
int backward = last - 1;/* a[last]は枢軸に充てる */
register char pivot = a[backward--];
/* 配列の要素が1個なら大小のグループ分けを終了する */
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ベストアンサー
- 回答日時:
>取り敢えず自分ではfirstは配列aの最前列要素の添え字、
>lastは配列aの要素数と考えたのですが…。
違います。
first、lastは、文字通り「最初の要素番号」と「最後の要素番号+1」を指定します。
>/* 左側のグループをさらに大小のグループに分類する */
>QAscendingSort(a, first, forward);
>/* 右側のグループをさらに大小のグループに分類する */
>QAscendingSort(a, forward + 1, last);
の部分は「forwardを境に、左グループと右グループを処理」してます。
最初に与えられたlast(これは「int n = sizeof(a) / sizeof(char);」の式により「最後の要素番号+1」になる)は、最後の最後まで変化しません。
もしlastが「最後の要素番号+1」ではなく「要素数」であるなら「先頭の要素番号を変えたなら、要素数も変えなければならない筈」です。
引数は、以下のような値が渡される筈です。
・最初の呼び出し: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(1要素の型)」と同じ形をした式だったので「lastは要素数」だと勘違いしたのでしょう。
ですが、本当は「lastは最後の要素位置+1」です。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# c言語 プログラムのエラー 1 2023/02/11 20:31
- C言語・C++・C# c言語の問題の説明、各所ごとに 5 2023/07/26 11:03
- C言語・C++・C# C 言語の Gauss Jordan 法について 2 2022/12/28 11:16
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- C言語・C++・C# c言語配列の結合についてです。 なぜうまくいかないのでしょうか。 #include <stdio.h 4 2022/05/30 22:42
- C言語・C++・C# C言語の課題が出たのですが自力でやっても分かりませんでした。 要素数がnであるint型の配列v2の並 3 2022/11/19 17:41
- C言語・C++・C# このプログラミング誰か教えてくれませんか 1 2022/06/02 15:27
- C言語・C++・C# 宣言する関数の形が決まっている状態で、 str1とstr2の文字列をこの順に引っ付けてstrに保存し 2 2022/05/30 18:21
- C言語・C++・C# c言語の問題です 課題1 (二分探索木とセット) 大きさ size の配列 array を考える。す 2 2023/01/10 21:08
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
IF関数でEmpty値を設定する方法。
-
VBAで配列の計算
-
パソコンキーボードで時分秒を...
-
VBで作った乱数を一度も重複さ...
-
VB.net 引数で配列変数を渡す際...
-
変数を動的に作るには?
-
Excel VBAで配列の途中から(X)M...
-
EXCEL VBA で、0から?1から?
-
配列の要素数を超えた参照のコ...
-
配列をリサイズする
-
C言語で3次元配列の課題をして...
-
10進数を4桁のバイト配列に格納...
-
C言語 重複しない4ケタの乱数...
-
動的配列が存在(要素が有る)か...
-
2次元配列の、黒いマス目で囲...
-
コンバートした画像をポリゴン...
-
C#の質問
-
C# 配列のスタックは可能でしょ...
-
複数のテキストボックスに同じ...
-
ラジオボタンのチェックをEnter...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
VBAで配列の計算
-
パソコンキーボードで時分秒を...
-
IF関数でEmpty値を設定する方法。
-
EXCEL VBA で、0から?1から?
-
変数を動的に作るには?
-
動的配列が存在(要素が有る)か...
-
VB.net 引数で配列変数を渡す際...
-
遅延バインディングを使用でき...
-
VBで作った乱数を一度も重複さ...
-
複数のテキストボックスに同じ...
-
配列の要素数を超えた参照のコ...
-
C言語 重複しない4ケタの乱数...
-
For文と配列
-
C#の質問
-
VBでbyte配列型のインスタンス...
-
Excel VBAで配列の途中から(X)M...
-
マップチップの当たり判定の出し方
-
ジャグ配列とは
-
五目並べのプログラムを配列と...
-
10進数を4桁のバイト配列に格納...
おすすめ情報