Javaでボゴソートを作ってみた

ボゴソートの概要

• ソートアルゴリズムの一つ
• 配列内の要素を、シャッフルして昇順か降順で並び続けるまでひたすら繰り返す
• 完了するまでかかる時間は非常に長く、最悪無限になる可能性もある。
• 実用性は無く、遊びのネタ

手順

• 整数型のListを用いて、ソートを行う
• 昇順に並ぶまで、シャッフルを行う
• 昇順に並んだら、終了

開発環境

• Windows 10
• OpenJDK 15.0.2

ソースコード

BogoSort.java

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class BogoSort {
    public static void main(String[] args){
        //初期化
        List<Integer> list = Arrays.asList(5,1,2,3,4);
        //trueが返されるまで、ひたすら繰り返す
        while(isAscendingOrder(list)==false){
            // シャッフルを行うメソッド
            Collections.shuffle(list);
            // 途中経過が見れる
            System.out.println(list);
        }
    }

    //List内の要素の並びが昇順ならば、trueを返す
    public static boolean isAscendingOrder(List<Integer> list){
        int i=0;
        for(;i<=list.size()-2 && list.get(i)<=list.get(i+1);i++);
        if(i==list.size()-1){
            return true;
        }
        return false;
    }
}

動かしてみる

時間を計測して、どのくらい時間がかかるかを測定してみる
まず、ソースコードを次のように変更

    public static void main(String[] args){
        long startTime = System.currentTimeMillis();
        List<Integer> list = Arrays.asList(5,1,2,3,4);
        while(isAscendingOrder(list)==false){
            Collections.shuffle(list);
            //System.out.println(list);
        }
        System.out.println(list);
        long endTime = System.currentTimeMillis();
        System.out.println("処理時間:"+(endTime-startTime)+"ms");
    }

listに代入する要素の内容、個数別に計測する
昇順になったlistの内容と、処理時間を表示する
スペックは割愛

結果

• 要素数5個の場合(内容:5,1,2,3,4)

[1, 2, 3, 4, 5]
処理時間:2ms

10回実行したが、0～2ミリ秒で終わった

• 要素数6個の場合(内容:6,1,2,3,4,5)

[1, 2, 3, 4, 5, 6]
処理時間:2ms

1～6ミリ秒で終わる

• 要素数10個の場合(内容:10,1,2,3,4,5,6,7,8,9)

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
処理時間:856ms

最小2ミリ、最大で約3000ミリ秒もかかった

• 要素数11個の場合(内容:11,1,2,3,4,・・・10)

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
処理時間:10161ms

3回試行した結果が、5000ミリ秒台が2回、10000ミリ秒台が１回だった

感想

ボゴソートがどのくらい効率が悪いのかが体感できました。
15個以上はいつ終わるか分からなかったので測定できませんでしたが、非常に面白かったです。

参考にしたサイト - 追記(2021/4/13)

載せ忘れてたので、追記しました。
ボゴソート - Wikipedia
Java - 配列をシャッフルする - 覚えたら書く