アルゴリズムとデータ構造第7回ソートソートの基本  ソートとは  データの集合を、キーとなる項目の値の大小関係に基づいて、ある一定順序に並べ替える作業小さい順：昇順  大きい順：降順  ソートの基本  ソートの安定性  等しいキー値を持つデータの位置関係ソート前後でも保持：安定なソート  ソート前後で不確定：安定ではないソート   内部ソートと外部ソート  内部ソート  すべてのデータが1つの配列上に格納可能な場合  外部ソート  データが大量で1度に並べ替えられない場合単純交換ソート  単純交換ソートとは  隣り合うデータの大小関係を順に比較し、必要ならば交換する作業を繰り返すことで並べ替え  別名：バブルソート 6 1 1 6 4 1 4 3 1 3 7 7 1 8 9 9 8 単純交換ソート  単純交換ソートのアルゴリズム  1回目のパスで、n-1回比較・交換  2回目のパスで、n-2回比較・交換  以下繰り返し、パスをn-1回行うことでソート完了   先頭からn-1個の要素がソート済みなら、n個目は自動的に決定安定性  隣り合う要素のみ交換するので安定単純交換ソート  単純交換ソートのプログラム  パス処理をn-1回実行するループを構成  iループ：0からn-2まで  各パスで比較・交換するループを内部に構成 jループ  末尾側から先頭側へ：jを末尾n-1からデクリメント  jとj-1の要素を比較、j-1が大きければ交換  kパス目ではjがkになるまで繰り返し：jはi+1まで  単純交換ソート  単純交換ソートのプログラム for (i = 0; i < n - 1; i++) for (j = n - 1; j > i; j--) if (a[j - 1] > a[j]) swap(&a[j - 1], &a[j]); 単純交換ソート  単純交換ソートの改良  あるパスで交換が1度も行われないとき、それ以降のパスでも交換は起きない→各パスで交換回数をカウントして0ならソート終了 1 3 6 4 4 6 7 8 9 単純交換ソート  単純交換ソートの改良プログラム for (i = 0; i < n - 1; i++) { int exchg = 0; /* 交換回数カウント */ for (j = n - 1; j > i; j--) if (a[j - 1] > a[j]) { swap(&a[j - 1], &a[j]); exchg++; } if (exchg == 0) break; /* 交換回数0なら終了 */ } 単純交換ソート  単純交換ソートの改良（2）  あるパスである時点以降交換がなかったら、その先はすでにソート済み→次のパスでソートすべき範囲が絞れる 1 3 9 4 9 4 6 7 6 7 8 6 8 単純交換ソート  単純交換ソートの改良プログラム（2） while (k < n - 1) { int j, last = n - 1; for (j = n - 1; j > k; j--) if (a[j - 1] > a[j]) { swap(&a[j - 1], &a[j]); last = j; } k = last; } 単純選択ソート  単純選択ソートとは  最小要素を選択し、それを先頭要素と交換  同様に次の最小要素を順次先頭側要素と交換 6 1 4 3 8 4 8 4 3 6 6 8 1 7 9 8 8 7 9 単純選択ソート  単純選択ソートのアルゴリズム  未ソ－ト部から最小のキー値を持つ要素を選択  選択した要素と未ソート部の先頭要素を交換  以上を未ソート部がなくなるまでn-1回繰り返し  安定性  離れた要素を交換することがあるため安定ではない単純選択ソート  単純選択ソートのプログラム for (i = 0; i < n - 1; i++) { int min = i; for (j = i + 1; j < n; j++) if (a[j] < a[min]) min = j; swap(&a[i], &a[min]); }