サイトマップ / Ｃ言語講座＞出入り口＞総目次＞目次：ポインタ＞単純選択ソート
ソート（sort）とは、データをある規則に従って並び替えることをいいます。例えば、辞書の項目はソートされています。数字を小さいものから順に（昇順）並べ替えること、大きいものから順に（降順）並べ替えること等がこれに当たります。
ソートには、プログラムを組むのは簡単だが速度の遅いもの、少し複雑だが高速なもの等、色々なアルゴリズムが案出され使われてきました。ソートの詳細はソートで学びます。
今日は数あるソートのアルゴリズムのうち、単純選択ソートによる文字列データのソートについて学びます。
単純選択ソートとは、最も小さい要素を探し、それと先頭の要素と交換します。これで、１番目の要素が確定しました。次いで２番目の要素について同じことを行い、２番目に小さい要素と入れ替えます。これを続けていくと、順次小さいものから確定していきます。比較する要素がなくなれば、ソートが終了します。
void StrSort( )がその関数です。ソートの途中経過を表示するなどして、すこし複雑なので、その骨組みを下記に示します。要素数nの配列をソートするとします。
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
i 番目の要素よりj番目の要素が小さければ、入れ替える。
}
}
２重のforループになっています。外側のforループで、交換の対象となる要素を指定します。内側のforループで、それ以降の要素と大小の比較を行っています。
iの初期値は０で、iが０の時、jは１から n - 1 の値をとります。なお、要素数nの配列の末尾の要素の添字はn - 1です。配列の先頭の要素と残りの全ての要素が比較される訳です。内側のループから抜けた時点で、str[0]に最も小さい要素が入ります。iの値が１になると、jは２からn-1の値をとります。内側のループから抜けた時、２番目の要素に２番目に小さい値がはいります。分かりやすいアルゴリズムだと思います。
今回は、文字列の大小の比較なので、strcmp( )を使います。
今回のソートはポインタの指す文字列の比較を行っているだけで、文字列のメモリ上の位置は変わりません。ポインタの入れ替えを行っているだけです。 */
#include <stdio.h>
#include <string.h> /* strcmp( )に必要 */
#define NUM_DATA 10 /* ソートするデータ数 */
/* ソート対象の文字列へのポインタの配列 */
char *animal[NUM_DATA] = {"Cat", "Dog", "Tiger", "Bug", "Bird",
"Fish", "Seep", "Cow", "Pig", "Rat"
};
void StrSort(char *str[ ], int n);
void main(void);
/* n個の文字列をソート */
void StrSort(char *str[ ], int n)
{
int i, j, k;
char *temp; /* 作業用ポインタ */
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
if ((strcmp(str[j], str[i])) < 0) {
temp = str[i]; /* 作業用ポインタを使い */
str[i] = str[j]; /* i + 1番目に小さい要素と */
str[j] = temp; /* str[i] の要素と交換 */
}
}
for (k = 0; k < n; k++) /* ソートの途中経過を表示 */
printf("%s ", str[k]);
printf("\n");
}
}
void main(void)
{
int i;
printf("ソート前: ");
/* ソートの対象を表示 */
for (i = 0; i < NUM_DATA; i++)
printf("%s ", animal[i]);
printf("\n\n");
printf("ソート開始\n\n");
StrSort(animal, NUM_DATA); /* animalは配列の先頭アドレス */
printf("\nソート後: "); /* ソート結果を表示 */
for (i = 0; i < NUM_DATA; i++)
printf("%s ", animal[i]);
printf("\n");
}
|
/* ソースプログラムをコンパイルして実行してみると、ソーティングの途中経過が表示されます。よく見ると、最初の要素が最初に確定され、次いで２番目、３番目というように、配列の添字の小さいものから順に確定していくのがわかります。
このソートのアルゴリズムでは、実行に要する時間はデータの並び方の影響を受けません。データの個数が決まれば、実行時間が決まります。
ここまで主としてchar型のポインタを例に学んで来ました。他のデータ型のポインタ、メンバに構造体へのポインタを含む構造体など、まだ学んでいない様々な形のポインタがあります。それらについては、今後の学習の過程で、随時、学んでいきます。 */
/* (C) 2000- ＹＦプロ. All Rights Reserved. */ 提供：Ｃ言語講座−それ自体コンパイルできる教材を使った講座です−