単純挿入ソート (Shuttle Sort)
ブログエントリーさぼらないために比較的よく知られているシンプルなアルゴリズムを書いてみた。
単純挿入ソート (Shuttle Sort) を書いてみました。
特徴としてトランプのカードを順番に並び替えるようなアルゴリズムであり、安定であること。
効率はあまり良くなく、O(n^2) です。
具体的には i 番目の要素（０番目からじゃない) に着目して i –1 番目と比較してそれより小さければ後ろにずらして挿入する。
これを繰り返しているだけの単純なアルゴリズムです。
特別にトリッキーなことはしてなくて理解しやすいアルゴリズムですね。
プログラムにはソートされていく過程をトレースして出力させています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
package jp.yucchi.shuttlesort; import java.security.SecureRandom; import java.util.Arrays; import java.util.stream.IntStream; /** * * @author Yucchi */ public class ShuttleSort { /** * @param args the command line arguments */ public static void main(String[] args) { int[] randomNumber = new SecureRandom().ints(10L, 1, 11).toArray(); System.out.println("befor:" + Arrays.toString(randomNumber) + System.getProperty("line.separator")); insertionSort(randomNumber); System.out.println(System.getProperty("line.separator") + "after:" + Arrays.toString(randomNumber)); } private static void insertionSort(int[] randomNumber) { IntStream.range(1, randomNumber.length).forEach(i -> { int j; int temp = randomNumber[i]; for (j = i; j > 0 && randomNumber[j - 1] > temp; j--) { randomNumber[j] = randomNumber[j - 1]; } randomNumber[j] = temp; trace(randomNumber); }); } private static void trace(int[] randomNumber) { System.out.println("trace:" + Arrays.toString(randomNumber)); } } |
このプログラムの実行結果は下図のようになります。
ちなみに Java8 を使っているので for 文でいいところを IntStream を使ったりしてます。
比較、入れ替えの for 文のところを Stream API を使ってできないものかと考えてみたのですが良いアイディアが浮かびませんでした。
配列の要素を並び替えるだけなので出来そうな気がしたのですが・・・（力不足、知恵不足、お小遣い不足）（ヲヒ
あっ、Stream API にはもちろん標準で sort の機能はあります。
だから本当はこんなアルゴリズム使う必要はありません！
そこんところ ヨロシク！ by 永ちゃん
あと、乱数配列の生成は public IntStream ints(long streamSize,int randomNumberOrigin,int randomNumberBound) メソッドを使って生成しました。
超便利です！
今回もありきたりネタでした。(^_^)
TAGS: Java | 2015年2月5日7:07 AM
Trackback URL