Javaで昇順に並び替え（挿入ソート）

f:id:ts0818:20190516210925j:plain

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

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

挿入ソートって？

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

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