並べ替えのアルゴリズム
予備知識
はじめに
この記事では並べ替えのアルゴリズムの中でも基本的なものを紹介します。
具体的には以下5つのアルゴリズムです。
配列の最大要素数が5のときの例を表で掲載
- バブルソート
- 選択ソート
- 基数ソート
配列の最大要素数が10のときの例を表で掲載
- バケットソート
- 分布数え上げソート
ソートとは並べ替えを意味する横文字です。
これらアルゴリズムの計算量について[最善,最悪,平均]の区別はありません。
[バケット,分布数え上げ]ソートについては、空間計算量が大きいため例外的に記載します。
基数ソートについても空間計算量は無視できるものの、上記2つに関連するため記載します。
並べ替えのアルゴリズムで出来ること
データ構造を昇順または降順に並べ替える
※ここでデータ構造は配列とする
計算対象選別
判定 | 計算対象 | 関係 | 基準値 |
---|---|---|---|
○ | データの比較回数 | ≧ | データの交換回数 |
データの交換回数 | = | 配列の中身により異なる | |
関数の呼び出し回数 | = | 確定値の決定回数 |
共有変数定義
変数にする対象 | 変数 | 関係 | 数値 |
---|---|---|---|
配列の最大要素数 | > | 1 | |
配列の数値範囲 | |||
比較回数の総和 |
※基数ソートの場合のみmは配列の最大値の桁数を意味する
バブルソート
このアルゴリズムでは隣接する2つの要素を順番に比較していくことで配列を並べかえる
その有り様が泡の動きに似ていることからバブルソートと呼ばれる
最大値を基準として配列を昇順に並べ替え
最小値を基準として配列を降順に並べ替え
比較基準の異なるバブルソート
※黄色は要素の交換が発生する部分
表のように同じバブルソートでも比較基準が異なる場合で違う形になる
この表では最小値を基準とする昇順バブルソートを示す
同じように最大値を基準とする降順バブルソートもある
一般化
配列の最大要素数が5のとき昇順または降順の表より
比較回数の総和Sは
漸近計算量は
※公式を元の形のまま適用するためには例の場合で総和が1~4までの和と捉えると分かりやすい
選択ソート
このアルゴリズムでは比較している時点までの最小値を基準とするため
交換回数は確定値が決まるごとに最大でも1回ずつで済む
比較回数はバブルソートと同じである
比較基準の異なるバブルソートの例のように
バブルソートでは確定値が決定するとき以外でも交換が発生するので交換回数は8回である
同じ配列において
選択ソートでは確定値が決定するときだけ交換が発生するので交換回数は4回である
よって選択ソートはバブルソートと比べて交換回数が少ない
最小値を基準として配列を昇順に並べ替え
最大値を基準として配列を降順に並べ替え
一般化
バブルソートの一般化と同じになるため省略する
前述のとおり交換回数はバブルソートより少ない
基数ソート
基数とは数値のもとになるもので0~9の数字である
基数を用意して配列を先頭から分別していく
配列の要素の数値の桁数が多い場合には桁数の数だけ分別を繰り返す
一の位から順番に分別することで並べ替えが完了する
計算量が分かりやすいように比較順番に合わせた表になっている
実際には各基数のところに配列の各要素が縦ならびで並べ替えられていく
各位の数で同じ数字であるときは先に分別した方から左側に詰めて並べる
例えば301と501の1の位は同じなので配列の先頭の要素の値が301のとき
他の数値も交えて書いてみると
基数 | 優先席 | 次席 | … |
---|---|---|---|
0 | 100 | ||
1 | 301 | 501 | |
2 | 502 | ||
… |
一般化
表のとおり
漸近計算量は
空間計算量として基数分の
バケットソート
このアルゴリズムを使うには前もって配列の要素に入る数値の範囲が分かっている必要がある
例えば1~5であると分かっている場合には
まずバケツを5つ用意して1~5の番号を記入する
そして配列を先頭の要素から順番に比較していき
要素内の数値を確認して用意されたバケツのうち同じ番号のバケツに分別していく
ここで言う用意されたバケツが数値範囲に該当する
一般化
表のとおり
漸近計算量は
空間計算量として
分布数え上げソート
このアルゴリズムを使うには前もって配列の要素に入る数値の範囲が分かっている必要がある
基本的な構造はバケットソートに似ているが数値範囲としてバケツではなくキーを使う
バケツに番号を記入するのは同じで配列の要素を分別したときに個数を記録していくことが特徴である
すべての記録が終了したら記録された個数をもとに配列の並べ替えを完了する
個数を記録する鍵的な仕組みから数値範囲を「キー」と呼ぶ
一般化
記録終了までの比較と記録終了後のキーを参照する回数を足し合わせた計算量がかかる
具体的には比較はn回で参照はm回なので
漸近計算量は
空間計算量として
Discussion