出席の確認はOpenLMS の 3 限のコマを用いて行う． 3限の授業時間中に出席登録を完了せよ．
この授業のトップページから レポートのページに移動し， レポートの提出状況を常に確認せよ．
整列とは，レコードの集合をキーの値の大小に従って 並べ替えること．広い分野で必要となる操作なので古くから アルゴリズムが研究されてきた．
整列アルゴリズムはいくつかの見地から分類できる． （p.178 Fig. 11.1）
外部整列はハードディスク等の外部記憶にあるデータを整列する アルゴリズムである．主記憶にあるデータと比較して 外部記憶にあるデータへのアクセスは桁違いに時間がかかる， また外部記憶は順番にアクセスする場合に比較的高速であるが， ランダムアクセスを行うと極端に効率が悪くなる，等の特徴がある．
これらの特徴から外部整列アルゴリズムはデータに対して頭から 順番にアクセスするシーケンシャルアクセスを前提としている．
この2つは，効率を比較する以前の問題として， 前提が異なる．一般に，整列アルゴリズムというと，
という操作を繰り返すだけで整列できるものを指す．これを 比較による整列と呼ぶ．
比較によらない整列は整列対象について
といった強い限定がある特殊な場合だけに使う事ができる整列である．
特に断らない限り整列アルゴリズムと言った場合は 比較による整列アルゴリズムを指すものとする． 比較による整列アルゴリズムについては $n$ 個のレコードを整列するのに 比較と交換の回数として $O(n \log n)$ の計算量が必要なことが証明されている．
比較によらない整列アルゴリズムでは，$O(n)$ で整列できるものがある．
比較による整列の内部整列には多くの種類のアルゴリズムがある． 計算量が $O(n^2)$ と大きいがアルゴリズムが簡単なものが いくつかあり，「単純なアルゴリズム」と呼んで分類する． 例としてはバブルソート，選択ソート，挿入ソート がこのグループに属する．
比較による整列の計算量の下限である $O(n \log n)$ を実現する アルゴリズムを「高速なアルゴリズム」と呼んで分類する． クイックソート， ヒープソート， マージソートがそのグループに属ずる．
シェルソート は $O(n^{1.5})$ 程度で， 「高速なアルゴリズム」と「単純なアルゴリズム」の中間的存在である．
マージソートは外部整列に適したアルゴリズムである．
比較による整列アルゴリズムの処理時間の内訳は，
を繰り返すことで占められる．
アルゴリズムによって比較は多いが交換が少ないもの， またその逆もありうるので，実際のデータに応じて選択 する必要がある．
計算量のオーダーだけで比較してはいけない．$O(n \log n)$ の高速なアルゴリズムは計算量でみると効率的だが， 実際には技巧を凝らした複雑なアルゴリズムであるために 定数項部分が大きいものが多い．具体的には小さい要素数の 整列ではオーダーでは劣る単純なアルゴリズムのほうが 高速に処理できることがある．
同点のキーのレコードについて，整列前の順序を保存することが 保証されているアルゴリズムを 安定なアルゴリズムという．（p.183 Fig. 11.2 参照）
安定であるかどうかは地味な違いに見えるが，複数のキーで 整列する場合には決定的に重要な性質である． 例えば，人物のレコードを年齢順に並べ， 同じ年齢の人物は50音順に並べる，という操作を行いたい場合， 安定なアルゴリズムであれば 50 音順に整列した後に 年齢順に整列するだけでよい．
クイックソートは高速だが安定でない．
バブルソート，選択ソート，挿入ソートの 3 つについて 説明する．オーダーはいずれも $O(n^2)$ と 効率的でないが，原理が簡単である．
バブルソートと挿入ソートは安定なアルゴリズムである．
bubble_sort（バブルソート）, selection_sort（選択ソート）, insersion_sort（挿入ソート）のサンプルプログラムが List 12.1, 12.2, 12.3 として収録されている．
いずれも同じ前提がある．キーは int 型であり，第 1 引数 としてこれから整列を行いたい配列が渡され， 第 2 引数には要素数が渡されるとする． 整列されたデータはもとの配列に格納される． つまり，呼び出された前と後で配列の内容が変更される．
List 12.1 の関数 bubble_sort の第 1 引数のように 「int a[]」と書くと仮引数 a は配列 a を表すポインタ となるが，具体的には各要素が int 型の配列の先頭アドレス が a に渡される．ポインタで渡されるので a[添え字] の形で すべての要素を読むことも変更することもできる． これを利用して関数内から呼び出された main 側の配列 の内容を変更することができる． 関数の引数としてポインタを渡すことは C の特徴的なポインタの使い方で，
に使われる．scanf の引数は後者の代表例である．
n 個の要素がある場合， C の慣習に従って配列の 0 番目に最初の要素が， n-1 番目に最後の要素が格納されていることに注意せよ．
配列の後ろから先頭に向かって，大小関係をチェックし，逆転していたら 入れ替える操作を基本とするアルゴリズムである．
原理は，まず最後の要素 a[n - 1] とその前の要素 a[n - 2]のペア を比較し，昇順になっていない場合は入れ替える．次に a[n - 2], a[n - 3] のペアを比較し，同じように昇順になるように 必要なら入れ替えを行う．この処理を最初のペア a[1], a[0] まで 行えば a[0] には最小値が格納されていることになる． この処理をループで書くと以下のようになる．
for(j = n - 1 ; j >= 1 ; j--)
a[j-1]とa[j]を比較して
大小順が逆なら入れ替える
次にまた同じ処理を最後の a[n - 1], a[n - 2] のペアから 今度は 2 番目のペア a[2], a[1] まで行えば a[1] に 2 番目に小さい値が格納される．この処理をループで書くと 以下のようになる．
for(j = n - 1 ; j >= 2 ; j--)
a[j-1]とa[j]を比較して
大小順が逆なら入れ替える
これを n-1 回繰り返すことで全体を整列させる アルゴリズムである．ループを書き連ねるなら，以下のようになる
for(j = n - 1 ; j >= 1 ; j--)
a[j-1]とa[j]を比較して
大小順が逆なら入れ替える
for(j = n - 1 ; j >= 2 ; j--)
a[j-1]とa[j]を比較して
大小順が逆なら入れ替える
・
・
・
for(j = n - 1 ; j >= n - 1 ; j--)
a[j-1]とa[j]を比較して
大小順が逆なら入れ替える
for 文の終了条件の右辺をループ変数 i とおいて 同じ処理の繰り返しとして書けるので，以下の 2重ループで処理できる．
for(i = 1 ; i <= n - 1 ; i++)
for(j = n - 1 ; j >= i ; j--)
a[j-1]とa[j]を比較して
大小順が逆なら入れ替える
このループは教科書p.186 List12.1 の 5,6 行目の ループと同じ処理を行う．
p.186 List12.1 を動作させるのが目標だが， まずプロトタイプ宣言について説明する．
C では関数は使うよりも前の行で定義されていなければ ならないというのが原則である．前々回までに授業で作成した プログラム例は
という条件を満たしている．この場合， 関数は使うよりも必ず前に定義される．
しかし，関数が関数を呼ぶ場合は注意が必要である． 例えば 前回の練習9.1, 9.2 で作成したハッシュのプログラムでは insert, delete 関数が hash, keyequal 関数を呼ぶので hash, keyequal 関数を先に書いた．
呼ばれる関数が前の行で定義されていないと， コンパイル時に戻り値等の判断が正確に出来ないという意味の警告が出力される． プログラムの規模が 大きくなると，どの関数がどの関数から呼ばれるかを 正確にチェックして正しい前後関係になるように関数を 配置するのは現実的でない．
そこで一般的には関数定義の前に全ての関数の 引数，戻り値の宣言だけを行うプロトタイプ宣言 を記述する．プロトタイプ宣言は関数定義の書き出しだけを 取り出した形になっている．プロトタイプ宣言では 型情報だけが必要なので書かれるパラメータ名は 実際の関数定義と異なっていても良い． ここからは，この授業では必ず関数定義の前に すべての作成する関数のプロトタイプ宣言を行うこととする．
具体的に，関数 bubble_sort のプロトタイプ宣言は
void bubble_sort(int a[], int n);
図10.1 bubble_sort のプロトタイプ宣言
である．第1引数は整数型配列へのポインタ，第 2 引数は 整数型であり，戻り値が無いことを示している．これを 全ての関数定義の前に置く．
この他，チェック用に配列の要素を全て出力する関数 print_array とそのプロトタイプ宣言も追加する． print_array は整数型配列へのポインタ a と整数 n を 引数とし，配列の要素 a[0] から a[n - 1] を 空白を挟んで出力する関数である．
結局 List 12.1 の前に標準入力ヘッダのインクルードと bubble_sort, print_array のプロトタイプ宣言である以下 を挿入し，
#include <stdio.h> void bubble_sort(int a[], int n); void print_array(int a[], int n);
図10.2 List12.1 の前部分
print_array 関数とテスト用の main である以下の 部分を List 12.1 の後に挿入すればテストプログラム は動作する．
void print_array(int a[], int n)
{
int i;
for (i = 0; i <= n - 1; i++){
printf("%2d ", a[i]);
}
printf("\n");
}
int main(void)
{
int data[10];
data[0]=20;
data[1]=6;
data[2]=55;
data[3]=74;
data[4]=3;
data[5]=45;
data[6]=13;
data[7]=87;
data[8]=46;
data[9]=30;
print_array(data, 10);
bubble_sort(data, 10);
print_array(data, 10);
}
図10.3 List12.1 の後部分
プログラムの動作を確認せよ．また main 内で設定している配列の 内容を書き換えても正しく整列されることを確認せよ．
bulle_sort は 2 重ループからなり，計算量は $O(n^2)$ であることがわかる．
未整列の場所の中の最小値を探し， a[0] から順に確定させていくアルゴリズムが 選択ソートである．
見つかった最小値の要素と 正しい置き場所の要素の交換を行うため， 最小値の要素の添字を記憶する必要がある． （変数lowest）
オーダーはバブルソートと同じ $O(n^2)$ だが，交換の回数は少ない．交換にコストがかかる場合は バブルソートより高速に動作する．
List 12.2 の選択ソートを動作させよ． 練習10.1 と同様の追加を行うことで動作させることができる． 但し，プロトタイプ宣言と main でソート関数を呼び出す部分の 2 箇所の関数名を bubble_sort から selection_sort に変更する必要がある．
配列の一部をソート済みに保ち， 新しく追加する要素を落ち着くべき位置に 挿入させるアルゴリズムが挿入ソートである．
挿入ソートもオーダーは $O(n^2)$ であるが， ある程度整列された配列を整列する場合に高速であるという 特徴がある．この特徴を利用して改良したものがシェルソートである．
List 12.3 の挿入ソートを動作させよ．これも 練習10.1 と同様の追加を行うことで動作させることができる．
バブルソート，選択ソート，挿入ソートで 実際に整列を行った場合の実行時間が p.192 Table 12.1 に示されている．要素数が大きい領域では 増加率は計算量のオーダー $O(n^2)$に従っていることが わかる．
p.192 Table 12.2 は比較と交換の起こった回数を求めたもの である．選択ソートと挿入ソートを比較すると，比較回数では 挿入ソートが勝り，交換回数では選択ソートが勝ることが わかる．バブルソートは両者の劣る点を併せ持つので 使用すべきではないことがわかる．
p.193 Table 12.3 はある程度整列されたデータに対して 3 つの整列操作を行ったときの実行時間である． 「ある程度整列されたデータに対して使うと速い」 という挿入ソートの性質がわかる．
第 10 回課題「区間の整列」 を提出せよ．