新しいソートアルゴリズム作ってみたよ！
ふとした瞬間に、ソートアルゴリズムを思いつきました。
「なんか、うまくいくんじゃね？」と思い、その辺の紙切れに少し流れを書いてみたところ、特におかしな点はなさそう。「じゃあ、実装するか！w」のノリで実装しました。
最近ネタ不足で、過去プログラムの紹介ばかりしていますが、これもその一つで、javaでの実装です。
これは大体１年前のものだった気がします。
アルゴリズムの名前は”ハノイソート”
この命名の理由は、二つのスタックを使ってソートを実現するその動きがハノイの塔を解く様に似ていたからです。
以下に、ハノイソートでソートを行う様子を示します。
アルゴリズムの解説
このソートアルゴリズムは、ソート用スタックと一時保存用スタックの二つのスタックを使います。
ソートの流れを以下に示します。
- ソート用スタックに値を１つ詰む
- ソート用スタックの中身をそのまま一時保存用スタックに入れ替える
- 入力配列の先頭の値を比較用変数に格納する
- 一時保存用スタックの値と配列の先頭の値を比べて、小さい方の値をソート用スタックに詰む
- 一時保存用スタックがからになるまで行う
- ２〜５を繰り返す
説明が下手くそなのはご容赦ください。
値の動きは上方のgif動画をみていただけるとわかりやすいかと思います。
とりあえず、スタックを駆使して、比較を挟みながら値を出し入れしています。
計算量の算出は余り自信ないですが、おそらくO(n^2)であると思いますので、優秀なソートではありません。
ちなみに、30000個の整数のソート時間をバブルソートと処理時間を比べたところ、
| ハノイソート | バブルソート |
|---|---|
| 3.997s | 1.53s |
という無残な結果に終わってしまいました。
計算量はO(n^2)以上あるのでしょうか？
自分で考えたと思ってるけど、もしかしたらすでにあるかも
僕も全てのソートアルゴリズムを知っているわけではありません。
もしかしたらすでに同じ仕組みのソートがあるかもしれないので、もし知っている方がいらしたらぜひ教えてください！
最後にクソコード投下
hanoi_sort.java
import java.util.*;
import java.io.*;
class hanoi_sort{
static int[] data;
public static void main(String[] args) {
int dataNum = 30000;
data = new int[30000];
String[] strarray = new String[30000];
int k = 0;
try{
File file = new File("numbers.txt");
BufferedReader br = new BufferedReader(new FileReader(file));
String str= null;
k = 0;
while((str = br.readLine()) != null){
strarray[k]=str;
data[k] = Integer.parseInt(strarray[k]);
System.out.println("[" + k + "]" + data[k]);
k++;
}
br.close();
}catch(FileNotFoundException e){
System.out.println(e);
}catch(IOException e){
System.out.println(e);
}
for(int i = 0; i < dataNum; i++){
System.out.println("[" + i + "]: " + data[i]);
}
System.out.println("--------------sort---------------");
Deque<Integer> dequeFirst = new ArrayDeque<>();
Deque<Integer> dequeSecond = new ArrayDeque<>();
int box = 0;
int count = 0;
int countF = 0;
boolean flag = true;
dequeFirst.push(data[0]);
countF++;
double start = System.currentTimeMillis();
for(int i = 1; i < dataNum; i++){
flag = true;
while(flag){
box = dequeFirst.pop();
countF--;
if(box <= data[i]){
dequeFirst.push(box);
countF++;
dequeFirst.push(data[i]);
countF++;
for(int j = 0; j < count; j++){
dequeFirst.push(dequeSecond.pop());
countF++;
}
count = 0;
flag = false;
}else{
dequeSecond.push(box);
count ++;
if(countF == 0){
dequeFirst.push(data[i]);
countF++;
for(int j = 0; j < count; j++){
dequeFirst.push(dequeSecond.pop());
countF++;
}
count = 0;
flag = false;
}
}
}
}
double end = System.currentTimeMillis();
for(int i = 0; i < dataNum; i++){
System.out.println("[" + i + "]: " + dequeFirst.pop());
}
System.out.println("sort time: " + (end - start) + "ms");
System.out.println("sort time: " + (end - start)/1000 + "s");
}
}
ちなみに入力はテキストファイルで、各行１つずつ整数が書いてある物を読み込むことで配列に数値を格納します（どこまでもクソ仕様）
こんな感じ↓
6418
18183
13643
6535
8436
3820
8969
19150
11902
4122
.
.
.
１年前のプログラムや発想はやはり見返すと恥ずかしいものです。
最後までお読みいただきありがとうございました！