ソートアルゴリズム：ボゴソートとは

ソートアルゴリズムとは

ソートアルゴリズムの意味は、ソートとアルゴリズムの意味を理解すれば分かります。

ソートとは、ある規則に則って、データを並び替えることを指します。

アルゴリズムは、ある課題に対してどのように解決するのかその方法や考え方を指します。

したがって、ソートアルゴリズムとは、バラバラのデータを規則的にどのように並び替えるのかという考え方のことです。

その中の１つであるボゴソートを紹介します。

今回は、バラバラの数値データを昇順に並び替えることを考えます。

ボゴソートとは

データの要素をシャッフルして、昇順になっているのか確認します。なっていなければ、再度、シャッフルという昇順に並び替えるまで、処理を行います。運しだいで処理時間が変わります。

最悪の場合、永遠に終わらないということもあります。

ボゴとは、bogusでインチキのという意味です。また、別名ランダムソートと呼ばれます。

プログラムで書いてみよう

Pythonでボゴソートのプログラムを書いてみようと思います。

import random

def bogo(data):
    length=len(data)
    while True:
        rdata=random.sample(data,length)
        for i in range(length-1):
            if rdata[i] > rdata[i+1]:
                break
        else:
            return rdata

data=[5,4,3,2,1]
print(data)
cdata=bogo(data)
print(cdata)

今回は、要素をシャッフルするので、ランダムモジュールをインポートします。

6行目でデータをシャッフルしています。ランダムに全要素を選択（重複なし）しています。

10行目のelseの部分はbreak以外で通った時に実行され、シャッフルしてソートされたデータを返します。

実行結果