はじめに
こんにちは。
突然ですが、「ソート（並べ替え）」と聞いて、みなさんはどんなアルゴリズムを思い浮かべますか？
バブルソート、クイックソート、マージソート…。世の中には実用的なソートがたくさんありますが、今日はとびきり非効率なソート、「ボゴソート（BogoSort）」について紹介します。
ボゴソートはジョークのようなソートアルゴリズムですが、そのシンプルで破壊的な発想はなぜかクセになります。理論的な計算量はなんと O(n*n!)。効率の悪さも桁違いですが、話のネタやプログラミングのお遊びとして知っておくと面白いソートです。
男は黙ってボゴソート！
ボゴソートってどんなソート？
ボゴソートは、配列（リスト）の要素をランダムに並び替えて、並び終わったリストがソート済みかどうかをチェックする、というものです。もしソートされていなければ、またシャッフルして…を繰り返します。ただそれだけ。とても原始的で“馬鹿らしい”と言われるのも納得です。
アルゴリズムの手順は以下の通りです。
- リストがソートされているか調べる
- ソートされていなければ、リストをランダムに並び替える
- 1に戻る
という超シンプル設計。「偶然」リストがソートされるまで永遠に繰り返すため、平均計算量はO(n×n!)と、ほぼ使い物になりません。
男は黙ってボゴソート！
そんなボゴソートですが、アイデアの“無謀さ”がなんともユニーク。せっかくなので、Wikipediaにも載っているトランプの例を、C言語で実装してみました。
このコードでは、ランダムな順番を作ってから、配列が昇順に並んでいるかどうかを確認しています。もし並んでいなければまた順番をシャッフルし、これをソート済みになるまでひたすら繰り返します。この仕組みのせいで、小さい配列でも気が遠くなるほど時間がかかることもあります。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void bogosort(int d[],int n)
{
int h=1,i,j,*k,*l;
k = (int *)malloc(sizeof(int)*n);
l = (int *)malloc(sizeof(int)*n);
memcpy(k,d,sizeof(int)*n);
while(h)
{
for(i=0;i<n;i++)
{
j=rand()%(i+1);
l[i]=l[j];
l[j]=i;
}
for(i=1,d[0]=j=k[l[0]];i<n;i++)
{
if(j>k[l[i]])break;
d[i]=j=k[l[i]];
if(i==(n-1)) h=0;
}
}
free(k);
free(l);
}
int main(void)
{
int list[] = { 132,45123,3462,36,43,5,2352,536,234,574 };
int i,size = sizeof(list) / sizeof(int);
bogosort(list,size);
for(i=0;i<size;i++) printf("%d\n",list[i]);
return(0);
}
おわりに
いかがでしたか？
実用性はゼロですが、ボゴソートは“究極の力技”でソートの本質や計算量について考えるきっかけになるアルゴリズムです。プログラミングの世界には、こうした「ジョークアルゴリズム」がいくつもあります。ネタやお遊びとして、たまにはこうした非常識な手法に触れてみるのも面白いですよ。
「男は黙ってボゴソート！」
そんな潔さを持ちつつ、実務ではもっと実用的なアルゴリズムを使うことをおすすめします。
コメント