授業で扱う基本的なソートアルゴリズムから、世界のおもしろいソートアルゴリズムを集めました。
マージソートとは、リストをいくつかに分割し、それぞれで整列させた後、今度はそのリスト同士を組み合わせてから整列させることで、最終的に1つの整列されたリストを実現するソートアルゴリズム。 計算量はO(n log n)で、安定したソートである。
バブルソートは隣り合う2つの要素の値を比較し、順序が逆だったら入れ替える操作を繰り返すことで、大きい値の要素を配列の末尾に移動させ、全体を整列させるソートアルゴリズムである。
ボゾソートとは、整列されていないリストから2要素を比較し、入れ替えた後に整列されていなかったらまた2要素の入れ替えをするのを繰り返すソートアルゴリズムである。今回は、入れ替え回数を30回を上限にしているが、効率が悪いアルゴリズムのためにその最悪計算時間はO(∞)となる。
ランダムに配列をかき混ぜることでソートされることを目指すソートアルゴリズムである。 特に並び替えのルールなどはなく、ランダムに配列を揃うまで並び替えるため、計算量は最悪の場合O(∞)となる。 ただし、今回の実装では長時間の処理を防ぐために30回を上限とし、30回でソートできなかった場合には空のリストを返すようにしている。 配列のデータ数が少ないとソートされる確率も高くなる。 非常に効率が悪いため、実用には不向きなソート方法と言える。 安定ではない。
基準値を一つ選び、リストをそれより小さい要素と大きい要素に分割し、 部分配列に対して再帰的に同じ操作を行って整列する。 平均計算時間はO(n log n)だが、最悪計算時間はO(n²)までなる。 安定ソートではない。
インサーションソートとは、データを未整列と整列済みに分けて、未整列の配列を順番に取り出して整列済みの配列の適切な位置に挿入していくことで並べ変えるソートアルゴリズムである。 計算量はo(n^2)であり、特別速いわけではないが小さな配列に対しては高速だったり、単純な実装で作れるため、しばしば利用される。 安定型。
サノスソートとは、宇宙の均衡を保つために、配列がソート済みかどうかに関わらず、ランダムに配列内の要素を半分消し去るソートアルゴリズムである。 残ったデータは半分(切り下げ)になった時点で「ソート済み」なので実際にはソートされていなくてもその時点で処理を終了する。 配列を破壊しているだけなので、本来のソートするという目的を果たせない。また、ランダムに半分消すため、同じ配列でも結果が変わる。 計算量はO(n)と非常に効率的なソートである。 もちろん安定ではない。
セレクションソートとは、未整列のデータ列から最小値を探し、それを配列の先頭要素と入れ替えていくことで並べ替えるソートアルゴリズムである。 計算量はO(n^2)と遅いため、一般的にはあまり優先されない。 しかし、空間計算量が小さいという利点もある。 安定ではない。