Javaで昇順に並び替え(挿入ソート)

f:id:ts0818:20190516210925j:plain

並び替えると言えば、ロイヤル・ストレート・フラッシュ!はい、どうもボクです。というわけで、Javaで挿入ソートにトライ。

そんでは、レッツトライ~。

 

挿入ソートって?

そも、挿入ソートって何ぞ?

Wikipediaさ~ん。

挿入ソートインサーションソート)は、ソートアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。

挿入ソートを高速化したソート法として、シェルソートが知られている。

挿入ソート - Wikipedia

だ、駄目やん... 遅いって言うてるやん...

アルゴリズム

まず0番目と1番目の要素を比較し、順番が逆であれば入れ換える。次に、2番目の要素が1番目までの要素より小さい場合、正しい順に並ぶように「挿入」する(配列の場合、前の要素を後ろに一つずつずらす)。この操作で、2番目までのデータが整列済みとなる(ただし、さらにデータが挿入される可能性があるので確定ではない)。このあと、3番目以降の要素について、整列済みデータとの比較と適切な位置への挿入を繰り返す。

挿入ソート - Wikipedia

ということらしい。 

 

実際に実装

してみますか。

judge.u-aizu.ac.jp

⇧  上記サイト様の問題で。

 

Eclipseを起動し、適当なJavaプロジェクト、クラスを作成で。

f:id:ts0818:20190516212601p:plain

そしたらば、ソースはこんな感じで。

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();
    } 
  }
}

んで、実行。

f:id:ts0818:20190516212935p:plain

んで、入力値は、

入力

入力の最初の行に、数列の長さを表す整数 N が与えられます。2 行目に、N 個の整数が空白区切りで与えられます。

挿入ソート | アルゴリズムとデータ構造 | Aizu Online Judge

となると。

f:id:ts0818:20190516213254p:plain

並び替えの経過が表示されました。

バブルソートと比較すると、「交換回数」は等しくなる。しかし、「比較回数」は、バブルソートでは必ずn(n-1) / 2回必要だったが、挿入ソートはこれ以下で済むため、挿入ソートの方が高速である。また、ほとんど整列済みのデータに対しては高速という特徴を持っている。

挿入ソート - Wikipedia

⇧  よく分からんけども、バブルソートよりは高速であると。

二分挿入ソート

挿入ソートの改良で、挿入するデータの前ではソートが済んでいるという性質を利用して、挿入する箇所を二分探索するというものである。データの量が少ないときにはあまり効果がないが、多いときには比較回数が少なくなる。探索アルゴリズムによっては不安定なソートになるが、工夫により安定させることが可能である。

挿入ソート - Wikipedia

⇧  データ量が多い時に役立つらしい。

 

ソートのアルゴリズムについては、

moneyforward.com

⇧  上記サイト様が詳しいです。 


ビッグデータとかの処理で注目されてる、分散処理ソフトウェアである「Apache Hadoop」では、

gihyo.jp

⇧  「ソートマージ結合」なるアルゴリズムを使っているらしい。

 だが、しかし!

ai-4-u.com

⇧  人気が低迷しているらしい...頑張れ!Hadoop!、負けるな!Hadoop

ということで、今回はこのへんで。