ボゴソート

ボゴソートは、ソートのアルゴリズムの一つ。平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。安定ソートではない。

アルゴリズム

トランプを順に並べる場合を例にすると、次のようになる。

1. トランプ52枚の束を放り投げて、ばらばらにする。
2. 1枚ずつ無作為にすべてを拾い集める。
3. ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。

カードをシャッフルし続けて、偶然一列に並ぶのをひたすら待ちつづけるアルゴリズムと考えてもよい。

疑似コード

function bogosort(array)
  while not is_sorted(array)
    array := random_permutation(array)

Perlによる実装

use List::Util qw(shuffle);
sub bogosort {
    my @array = @_;
    return unless @array;
    @array = shuffle @array
        until is_sorted(@array);
    return @array;
}
sub is_sorted {
    my @array = @_;
    return 1 unless @array;
    for my $i (0 .. $#array) {
        next unless defined $array[$i];
        next unless defined $array[$i + 1];
        return if $array[$i] gt $array[$i + 1];
    }
    return 1;
}

計算時間および停止性

すべての要素が互いに異なる場合、時間計算量はO(n×n!)となる。実際の計算時間は、等しい要素が含まれているか、そしてそれらがどのくらいの頻度で含まれているかに依存する。

アルゴリズムの停止性は無限の猿定理により保証される。ただし計算機で擬似乱数を用いて実行すると、入力によっては停止しない場合がある。