ソート

今回の資料には，理解の確認や考察の幅を広げるための「QUIZ(参考)」をいくつか設けています．あくまで，参考として示しているものです．特別な指示がない限り，最初は，読み飛ばしても結構です．

簡単なソート（数値型）

ソートの基本

ソートには色々なアルゴリズムがありますが，まず，動作確認のために，最も簡単なソートを書いてみましょう．もう少し賢いソートを実装してみたくなるかもしれませんが，それは少し置いて．

Listing 22 最も簡単なソートの例1 stupid-sort-int.c

void swap(int *a, int *b)
{
  int tmp;

  tmp = *a;
  *a = *b;
  *b = tmp;
}

/**
 * stupid sort for testing.
 */
void b_sort(int p[], int left, int right)
{
  int i, j;

  for (i = left; i <= right; i++) {
    for (j = left; j <= right - 1; j++) {
      if (p[j] > p[j + 1])
        swap(&p[j], &p[j + 1]);
    }
  }
}

int main()
{
  int data[] = {3, 2, 1, 4, 5};
  int length = sizeof(data) / sizeof(data[0]);  /* See K&R p.164 */
  int i;

  b_sort(data, 0, length - 1);

  for (i = 0; i < length; i++) {
    printf("%d ", data[i]);
  }
  printf("\n");
}

実行結果:

1 2 3 4 5

実行結果から分かる通り，これは，昇順のソートとなっています．

QUIZ(参考)：ところで，実行結果だけではなく，途中経過を示すことはできますか？例えば，Listing 22の17行目のforループ（外側のループ）直後で，実行結果と同等の配列内の数値表示をした場合，どのような表示が順番に得られますか？

ソートに必ず必要な要素は，以下の通りです．

1. ソートしたいデータ列dataを用意する

2. data中の 2つの要素間で大小比較をする

3. 2要素を入れ替える (大小関係，位置関係が期待通りでなければ)

これは，バブルソートであっても，クイックソートであっても同じです．

QUIZ(参考)：Listing 22のソースコードを見て，１～３が，それぞれどこに相当するか，答えられますか？

2要素の入れ替え(数値型)

入れ替える機能を持つ関数は，これまでにも例示しています（関数とポインタ）．復習しておきましょう．

Listing 22の例では，配列の中のデータを入れ替える関数はswap()として実装されています．2つのint型のポインタを引数に取り，ポインタで指す2要素を入れ替えます．

void swap(int *a, int *b)
{
  int tmp;

  tmp = *a;
  *a = *b;
  *b = tmp;
}

int main()
{
  int x = 1, y = 2;

  printf("Before: x = %d, y = %d\n", x, y);
  swap(&x, &y);
  printf("After:  x = %d, y = %d\n", x, y);
}

実行結果:

Before: x = 1, y = 2
After:  x = 2, y = 1

ポインタを使わずに，以下のように書いてはダメなのでしょうか．

void swap(int a, int b)
{
  int tmp;

  tmp = a;
  a = b;
  b = tmp;
}

int main()
{
  int x = 1, y = 2;

  printf("Before: x = %d, y = %d\n", x, y);
  swap(x, y);
  printf("After:  x = %d, y = %d\n", x, y);
}

実行結果:

Before: x = 1, y = 2
After:  x = 1, y = 2

入れ替わっていませんね．(箱x) と (箱y) 中の数字を入れ替えたいのに，中に記してある数 1 と 2 を知らされてもどうしようもありませんよね．(箱x) と (箱y) の場所（ポインタ）で教えてくれないと操作できません．*aとすることではじめて，指定された (箱a) の中身を操作できるのです．

QUIZ:上記の成功と失敗の違いが分かるような図を書いてみてください．例えば，下図のようなメモリ状態を起点として，両者の違いを説明できますか？

Figure 15 main関数実行直後のメモリの様子

簡単なソート（文字列型）

いきなり複雑な構造体に取り掛かるのは，大変困難です．

まずは，練習として，Listing 22のソートを参考にして，文字列型のデータに対するソートを試作してみましょう．

先ほども整理した３要素に着目すれば，以下のような点に気を付ける必要がありそうです．

• データ列：int型の配列ではなく，char型のポインタの配列である

• 大小比較： 数字としての大小比較はできないので，strcmp()関数を使う

• 要素入れ替え：数字（int型）ではなく，文字列（char型のポインタ）を入れ替え可能なswap()関数を作る

（「char型のポインタの配列」は「char*型の配列」と言い換えてもよいでしょう．）

順番に確認してみます．

データ列の用意

まずは，データ列の用意です．

Listing 22では，dataはint型の配列として与えられていました．

文字列をソートしたいのであれば，dataはchar*型の配列として与えればいいですね．

前者は，int型の配列，後者は，char型のポインタの配列，です．（char型の配列でも，char型のポインタでもありません．ポインタの配列，です．）

/* Example data of Integers */
int data[] = {3, 2, 1, 4, 5};

↓

/* Example data of Strings */
char* data[] = {"3", "2", "1", "4", "5"};

QUIZ(参考)：

int型の配列としての宣言＆初期化と，char型のポインタの配列としての宣言＆初期化で，それぞれの場合に，メモリ内の様子を図示できますか？（ヒント：図1.4，図2.2）

2要素間の大小比較（数値型と文字列型）

次に，2つの要素の大小関係を比較することを考えます．

数値型の比較

要素がint型の場合は，比較演算子<や>などが使えます．実際，前出の「Listing 22」では，>を使って，

if (p[j] > p[j+1])

としていました．移項すれば，以下のようにも書けそうです．

if (p[j] - p[j+1] > 0)

文字列型の比較

要素が文字列（char*）の場合は，どうでしょうか？%Fで使ったstrcmp()が，ここでも使えますね．例えば，%Fでは，strcmp()を以下のように使用していました:

if (strcmp(p->name, word) == 0 ...

これは，strcmp()は，2つの文字列が一致する場合に0を返す，という仕様を利用しています．ところが，この関数は，大小比較にも使うことができる仕様となっています．

$ man 3 strcmp

してみてください．以下は，その抜粋です．

int strcmp(const char *s1, const char *s2);

The strcmp() functions return an integer greater than,
equal to, or less than 0, according as the string s1 is
greater than, equal to, or less than the string s2.

つまり，

s1 > s2 なら → 正の数
s1 = s2 なら → ゼロ
s1 < s2 なら → 負の数

を返します．

従って，p[j]がint型の場合の比較:

if (p[j] - p[j+1] > 0)

に対して，p[j]がchar*型の場合は，

if (strcmp(p[j], p[j + 1]) > 0)

となるでしょう．

QUIZ(参考)：

int型の引数に対して，strcmp()と同等の戻り値の関数を作ることはできますか？

QUIZ(参考)：

文字列の「大きい」とか「小さい」とはどういう意味か，説明できますか？（ヒント：K&R pp.129-130 のstrcmp()の実装例，および，解説1.1）

2要素の入れ替え(文字列型)

数値型に対する入れ替え操作の理解，ならびに，文字列・配列・ポインタが理解できていれば，難しくありません．

考えてみてください．

QUIZ(参考)：

Figure 15のような図を描いて，文字列の swap を説明できますか？（ヒント：split()の実装に関する説明Figure 6）

実装例

以上を踏まえれば，例えば，以下のように書き換えられるでしょう：

Listing 23 最も簡単なソートの例2 stupid-sort-string.c

#include <string.h>
#include <stdio.h>

void swap(char **a, char **b)
{
  char *tmp;

  tmp = *a;
  *a = *b;
  *b = tmp;
}

/**
 * stupid sort for testing.
 */
void b_sort(char *p[], int left, int right)
{
  int i, j;

  for (i = left; i <= right; i++) {
    for (j = left; j <= right - 1; j++) {
      if (strcmp(p[j], p[j + 1]) > 0)
        swap(&p[j], &p[j + 1]);
    }
  }
}

int main()
{
  char *data[] = {"3", "2", "1", "4", "5"};
  int length = sizeof(data) / sizeof(data[0]);  /* See K&R p.164 */
  int i;

  b_sort(data, 0, length - 1);

  for (i = 0; i < length; i++) {
    printf("%s ", data[i]);
  }
  printf("\n");
}

実行結果:

1 2 3 4 5

うまくいっているようです．

QUIZ(参考)：Listing 22のソースコードから，順を追ってListing 23へと改造できますか？main()関数冒頭における，変数宣言の書き換えから始めて，修正内容を順番に説明してください．

// int data[] = {3, 2, 1, 4, 5};
char *data[] = {"3", "2", "1", "4", "5"};

QUIZ(参考)：構造体struct date型のソートを作ることもできますか？比較する関数の例は，既に説明しています．構造体の入れ替えの例は，次項で説明しています．これらの説明を読んでもできないという人は，ひとつ前のQUIZへの回答が不十分であるか，構造体の知識について復習が必要かもしれません．

%Sコマンド（cmd_sort() 関数）の検討

具体的に，%Sの実装をするためには，前節までの基本的なソートの考え方を理解しておく必要があります．

データ列の用意

今回，実装する%Sでは，ソートしたいデータ列とは，struct profileの配列です．つまり，struct profile profile_data_store[]として，既に用意されています．

2要素間の大小比較（構造体型）

次に，2つの要素の大小関係を比較することを考えます．

比較したい要素はstruct profileですが，一筋縄ではいかなそうです．難しい処理を考えるときはどうするんでしたっけ？（参考：課題プログラムの理解(3) : 段階的詳細化とコードへの変換）

まずは，%Fの時の考え方を思い出して，3種類のデータ型に分類して，基本的な比較方法を確認してみます．それから，本当にやりたかったことを考えていきましょう．

既に，数値型の比較と文字列型の比較の考え方は示しました．残るは，構造体であるstruct date型です．

構造体型の比較 1

struct date構造体は，日付を扱う型として考えてきました．実際，その考えに基づき，%Fにおいて，一致判定の処理を検討したはずです．

その考え方を踏まえて，strcmp()のような機能を持った関数を考えてみましょう．

数値としての大小関係，さらには，年月日の優先順位を意識すれば，例えば，以下のようなcompare_date()関数が思いつきます．

/**
 * Date compare function conforming to qsort(3).
 */
int compare_date(struct date *d1, struct date *d2)
{
  if (d1->y != d2->y) return d1->y - d2->y;
  if (d1->m != d2->m) return d1->m - d2->m;
  return d1->d - d2->d;
}

QUIZ(参考)：

なぜこの記述で，日付としての比較ができるのか，説明できますか？

ここで学んで欲しい事の1つは，

strcmp()やcompare_date()のような比較関数として用意し，利用する

ということです．そうすることで， %Fの実装例のように，if文の中に比較の列をズラズラ書かないで，関数1つを呼び出すだけで比較ができます．

構造体型の比較2

さて，%Sの実装の話に戻します．struct profile型の比較はどうしましょうか．

繰り返しになりますが，構造体どうしを単純に比較することはできません．メンバを参照しながら比較する必要があります．実際，%Fの実装においては，構造体の各メンバと検索対象の文字列wordを繰り返し比較することを考えました．

どういうルールで比較するのが妥当でしょうか？日付の場合は，年月日がいずれも数値ですし，大小関係も明確でした．struct profileの場合は，どうすればよいのでしょうか？

考えるためには，%Sの仕様を振り返る必要があります．課題説明書のPDFを読んでください．今回の名簿管理プログラムでは，struct profileの，どのメンバ同士を比較するかは，%Sの引数（以下，columnとします）として与える，という仕様がありました．

そこで，columnの値に基づいて比較対象をswitch構文で分岐させ，strcmp()やcompare_date()のような戻り値の仕様を持つ関数を考えてみましょう．

/**
 * Profile compare functions conforming to qsort(3).
 * cf. strcmp
 *  p1 > p2 : return greater than zero
 *  p1 = p2 : return zero
 *  p1 < p2 : return less than zero
 */
int compare_profile(struct profile *p1, struct profile *p2, int column)
{
  switch (column) {
    case 1:
      return p1->id - p2->id;   /* id */
    case 2:
      return strcmp(...);       /* name */
    case 3:
      return compare_date(...); /* birthday */
    case 4:
      return strcmp(...);       /* address */
    case 5:
      return strcmp(...);       /* comment */
    default:
      return ;                  /* What is appropriate treatment? */
    }
}

関数の引数，特に要素の型に注目してみましょう．ここでは，struct profileではなく，そのポインタ型struct profile *を引数としています．これは，ポインタを渡した方が効率がいいからです．

QUIZ(参考)：

なぜ効率がいいか，答えられますか？（参考：練習4-4 new_profile() 関数の実装）

より良い名簿管理プログラムにするための方法も考えてください．

例えば，columnが1から5を外れた場合(default:)は，今のままでよいのでしょうか？

現在のプログラム例でも（あるいは，default 名札（ラベル）を用意しなくとも），プログラムとしての実行そのものは可能です．仕様を満たした動作も実現されそうに見えます．gcc -Wallのコンパイル時点で警告が出ますが，それは置いておいて．

この関数での対応を考えるだけではなく，より上位の関数における対応も視野に入れた検討をすべきでしょう．例えば，「練習3-3 構文解析プログラムの簡単な動作テスト」で考えたような：

• exec_command()が持つべき機能とその処理

• cmd_print()における引数の処理の責任の所在

における考え方は，ここでの一案を考えるヒントになりそうです．

2要素の入れ替え（構造体型）

構造体は，「代入」することができます．（参考：代入演算子 = の扱い）

従って，struct profile型であっても，int型の場合と同じように，swap()関数を書くことができそうです．

void swap_profile(struct profile *p1, struct profile *p2)
{
  struct profile tmp;

  tmp = *p2;
  *p2 = *p1;
  *p1 = tmp;
}

しかし，この操作は，少し高価な(時間のかかる)操作であることを知っておきましょう．

int型の代入とは，単一の数値（sizeof(int)バイト）のメモリ転送をする操作，と理解できます．すると，構造体の場合は，それを構成する全要素（sizeof(struct profile)バイト）のメモリ転送が代入の度に起こっている，となります．（参考：第4回「構造体のメモリ効率」，次回「プログラムの改良　他」）

何かうまい方法があればよいのですが・・・？

ソートの動作確認

作成した %S がうまく動いているか，どうやって確認したらいいでしょうか．より確かそうな結果と %S の結果を比較したくなるでしょう．しかし，この際の問題は，2つあります．

1. より確からしい結果をどうやって得るか

2. より確からしい結果とどうやって比較するか

以下，順番に見ていきましょう．

より確からしい結果をどうやって得るか？

より確からしい結果をどうやって得るかについて，

• 別のアルゴリズムによる実装との比較

• 既存ソフトウェアとの比較

を紹介します．

別のアルゴリズムによる実装との比較

例えば，教科書のpp.105-106を参考にしてクイックソートを書いたり，p.75を参考にしてシェルソートを書いたとします．クイックソートやシェルソートは複雑なので，実装を間違えるかもしれません．

このような場合には，実装が楽な別のソート (簡単なソート) をもう1つ実装して，比較するという手があります．例えば， %S の代わりに %s というコマンドを用意して，%S の結果と %s の結果を比較してみてはどうでしょう．隣の人の実装と比較するという手もあるかもしれませんが，その場合は，隣の相手を見極めて(テストして)から決めましょう．

もう1つ別に実装するのは，少し遠まわりに感じるかもしれません．しかし，実際には，テストのための試作やデバッグのための隠しコマンドを用意することはよくあって，最終的なコードの前に書き捨てられる（あるいは，デバッグコードとして隠されている）コードの方が多い場合もよくあります．

サンプルプログラムdb-sample試作の過程では，%S コマンドの引数が，負の場合は，本ページで示した簡単なソート，正の場合はクイックソート，をそれぞれ実行するように書かれています．

既存ソフトウェアとの比較

ソートのためのコマンドといえば，UNIX のsortコマンドが，まず思い浮かびます．長年使われているsortは，自分の作った%Sコマンドより正確でしょうから，これと比較すればかなり安心です．

サンプルプログラムdb-sample試作の過程では，sortコマンドとの実行結果と比較しています．加えて，カラムを整形するために，cutやsedなども活用しています．

sortの活用例（発展的な内容です．余裕のある人だけクリックして読んでください．）

sortコマンドを使いこなせば，CSVファイルを，以下のようにソートすることもできる．

$ sort -t, -k2,2 sample.csv         # 2要素目=Name を文字列として，昇順ソート
$ sort -t, -k1,1 -n sample.csv      # 1要素目=ID を数値(-n)とみなして，昇順ソート
$ sort -t, -k3,3 -V sample.csv      # 3要素目=Birthdayを自然な数値(-V)として，昇順ソート

あるいは，表計算ソフト(Microsoft ExcelやLibreOffice Calcなど)が使える環境であれば，sample.csvを読込んで，好きな項目（カラム）でソートさせてみれば確認できます．ただし，テストを自動化するのは難しいかもしれません．

サンプルプログラムdb-sample試作の過程では，テストではなくデバッグの際に Excel も活用しています．

より確からしい結果とどうやって比較するか？

ここでは，『テストしやすい出力形式の検討』を考えてみましょう．

%Sコマンドの確認のために，%Pで出力してみて，db-sampleと比較したいとします．しかし，%Pは，ソートの正しさを確認するには不向きなコマンドです．例えば，以下のCSVからなるsort-sample.csvがあったとして，%S 4とした場合，正解は，どうなるでしょうか．

5100046,1Taro,2012-06-29,Okayama Japan,Hello
5100047,2Taro,1845-11-20,Kagawa  Japan,Goodbye
5100048,3Taro,1998-09-19,Okayama Japan,Hello
:

1Taroと3Taroの4カラム目は，どちらもOkayama Japanですから，%Sの結果として，どちらが前でも正解ですよね．したがって，以下に示す出力例1と出力例2は，どちらもソートできている，といえます．

出力例1	出力例2
Id : 5100047 Name : 2Taro Birth : 1845-11-20 Addr. : Kagawa Japan Comm. : Goodbye Id : 5100046 Name : 1Taro Birth : 2012-06-29 Addr. : Okayama Japan Comm. : Hello Id : 5100048 Name : 3Taro Birth : 1998-09-19 Addr. : Okayama Japan Comm. : Hello	Id : 5100047 Name : 2Taro Birth : 1845-11-20 Addr. : Kagawa Japan Comm. : Goodbye Id : 5100048 Name : 3Taro Birth : 1998-09-19 Addr. : Okayama Japan Comm. : Hello Id : 5100046 Name : 1Taro Birth : 2012-06-29 Addr. : Okayama Japan Comm. : Hello

あなたの作った%Sの結果が出力例1，別の実装が出力例2だったとします．しかし，この両者に違いがあること（あるいは，同一であること）を，diffコマンドなどで機械的に確認するのは難しいでしょう．

QUIZ(参考)：何が難しいのか，具体例を示しながら，その問題点を指摘し，解決が困難であることを説明することはできますか？あるいは，解決が難しくないのであれば，具体的な方法を説明してください．

機械的な方法では簡単にできないとなれば，目視に頼りたくなります．面倒なので，テストしたくなくなりますね．どうすればいいでしょうか？

例えば，テスト用の表示コマンド %t を用意する，というのはどうでしょうか．先程紹介したテスト用のコマンド %s を用意するのと同じ理屈です．

実際，db-sampleでは，出力結果を確認するために，あるカラムだけをそのまま出力するテストコマンドを用意しています．具体的には，%t 4というコマンドにより，4番目のカラム（Addr.）のみを一覧表示します．

Listing 24 テスト用コマンド%tの利用例（2–6行目は，標準入力への入力．7–9行目は標準出力への出力．）

$ ./db-sample
5100046,1Taro,2012-06-29,Okayama Japan,Hello
5100047,2Taro,1845-11-20,Kagawa  Japan,Goodbye
5100048,3Taro,1998-09-19,Okayama Japan,Hello
%S 4
%t 4
Kagawa  Japan
Okayama Japan
Okayama Japan

サンプルプログラムdb-sample試作の過程では，%tの出力結果と，sortコマンドの結果を比較することで，テストが楽になりました．

動作確認のまとめ

最後に．これまでの講義内容を振り返ってみれば，様々なヒントが見つかりそうです．

例えば，出力結果を比較するという方法ならば，以前行ったことのあるアレやコレを思い出してみても，何とかなりそうです．

「特定の○○のみ表示する」というのも，似たようなことを考えた記憶があります．

「○○と類似した関数を作る」という話も，やはり似たようなことを考えてきました．

いずれにせよ，ここでは動作テストのことを考えているわけですから，複雑すぎる実装にならないよう注意してください．動作テストそのものにバグを入れてしまっては，目もあてられません．