並び替えると言えば、ロイヤル・ストレート・フラッシュ!はい、どうもボクです。というわけで、Javaで挿入ソートにトライ。
そんでは、レッツトライ~。
挿入ソートって?
そも、挿入ソートって何ぞ?
Wikipediaさ~ん。
挿入ソート(インサーションソート)は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。
挿入ソートを高速化したソート法として、シェルソートが知られている。
だ、駄目やん... 遅いって言うてるやん...
アルゴリズム
まず0番目と1番目の要素を比較し、順番が逆であれば入れ換える。次に、2番目の要素が1番目までの要素より小さい場合、正しい順に並ぶように「挿入」する(配列の場合、前の要素を後ろに一つずつずらす)。この操作で、2番目までのデータが整列済みとなる(ただし、さらにデータが挿入される可能性があるので確定ではない)。このあと、3番目以降の要素について、整列済みデータとの比較と適切な位置への挿入を繰り返す。
ということらしい。
実際に実装
してみますか。
⇧ 上記サイト様の問題で。
Eclipseを起動し、適当なJavaプロジェクト、クラスを作成で。
そしたらば、ソースはこんな感じで。
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class InsertionSort { public static void main(String[] args) { // TODO 自動生成されたメソッド・スタブ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); try { int N = Integer.parseInt(br.readLine()); // 配列の大きさ String[] strArr = br.readLine().split("\\s"); // 文字列の配列 int[] intArr = new int[N]; // 数値の配列 // 数値の配列の各要素に、値を代入 for (int i = 0; i < N; i++) { intArr[i] = Integer.parseInt(strArr[i]); } int tmp = 0; // 退避用 int j = 0; // インデックス用 // 配列の大きさだけ繰り返し for (int i = 0; i < N ; i++) { // 配列の中身を表示 for (int k = 0; k < N; k++) { System.out.print(intArr[k]); // 配列の最後の要素以外は、半角スペースを付ける if (k != N -1) { System.out.print(" "); } } System.out.println(); // 配列の最後の要素になったら、並び替えせず、処理を抜ける if (i == N -1) { break; } // 並び替え tmp = intArr[i+1]; // 右隣の要素を退避しておく j = i; // 右隣の要素のほうが小さい場合 while (j >= 0 && intArr[j] > tmp) { // 入れ替え intArr[j+1] = intArr[j]; j--; } intArr[j+1] = tmp; } } catch (NumberFormatException e) { // TODO 自動生成された catch ブロック e.printStackTrace(); } catch (IOException e) { // TODO 自動生成された catch ブロック e.printStackTrace(); } } }
んで、実行。
んで、入力値は、
入力
入力の最初の行に、数列の長さを表す整数 N が与えられます。2 行目に、N 個の整数が空白区切りで与えられます。
となると。
並び替えの経過が表示されました。
バブルソートと比較すると、「交換回数」は等しくなる。しかし、「比較回数」は、バブルソートでは必ずn(n-1) / 2回必要だったが、挿入ソートはこれ以下で済むため、挿入ソートの方が高速である。また、ほとんど整列済みのデータに対しては高速という特徴を持っている。
なお交換回数に関しても、前記実装例のように一連の交換の途中の特定処理を省略することができるので交換一回が高速になる。また、特にデータが連結リストで格納されている場合には、バブルソートと比較して大幅な高速化が図れる。これは配列における「挿入」が一連の交換(の途中の特定処理を省略した処理)によって実現されるのに対し、連結リストでは文字通りの「挿入」が可能であるので、交換回数が大幅に減少するからである。
⇧ よく分からんけども、バブルソートよりは高速であると。
二分挿入ソート
挿入ソートの改良で、挿入するデータの前ではソートが済んでいるという性質を利用して、挿入する箇所を二分探索するというものである。データの量が少ないときにはあまり効果がないが、多いときには比較回数が少なくなる。探索アルゴリズムによっては不安定なソートになるが、工夫により安定させることが可能である。
⇧ データ量が多い時に役立つらしい。
ソートのアルゴリズムについては、
⇧ 上記サイト様が詳しいです。
ビッグデータとかの処理で注目されてる、分散処理ソフトウェアである「Apache Hadoop」では、
⇧ 「ソートマージ結合」なるアルゴリズムを使っているらしい。
だが、しかし!
⇧ 人気が低迷しているらしい...頑張れ!Hadoop!、負けるな!Hadoop!
ということで、今回はこのへんで。