ボゴソートによる整列を実装してみる

プログラミング

こんにちは。今回は完全にネタです。

ボゴソートとは

てきとーにシャッフルします。うまくソートされていたら、ソートが完了です。

ソートされるまでこの繰り返しをします。とにかく運だけが頼りです。

ボゴソートを実装してみる

ボゴソートを毎度のPythonで実装してみました。

import random
import copy

def bogo_sort( l ):
  count = 0
  while True:
    random.shuffle( l )
    count += 1
    if is_sort( l ):
      return l, count

def is_sort( l ):
  for i in l:
    if 'f' in locals() and f > i:
      return False
    f = i
  return True

def make_random_list( n ):
  a = []
  for i in range( n+1 ):
    a.append( random.randint( 1, 100 ) )
  return a


s = 0
a = make_random_list( 6 )
l = copy.deepcopy( a )
b , c = bogo_sort( a )
s += c
print( 'ソート前:', l )
print( 'ソート後:', b )
print( 'ソート回数:', c, '回' )

実行結果です。 

ソート前: [33, 45, 86, 61, 63, 30, 52]
ソート後: [30, 33, 45, 52, 61, 63, 86]
ソート回数: 662 回

ボゴソートでソートできるまでの回数

回数を数えてみることにします。プログラムは次のように変えています。

import random

def bogo_sort( l ):
  count = 0
  while True:
    random.shuffle( l )
    count += 1
    if is_sort( l ):
      return l, count

def is_sort( l ):
  for i in l:
    if 'f' in locals() and f > i:
      return False
    f = i
  return True

def make_random_list( n ):
  a = []
  for i in range( n+1 ):
    a.append( random.randint( 1, 100 ) )
  return a


times = 10000
for k in range( 2, 6 ):
  s = 0
  for t in range( 0, times ):
    a = make_random_list( k )
    b , c = bogo_sort( a )
    s += c
  print( k, '個のデータ 平均', s/times, '回' )

実行結果です。それぞれのデータの個数に対して10000回ずつ試行して、その平均回数を表示しています。 

2 個のデータ 平均 5.9195 回
3 個のデータ 平均 23.1151 回
4 個のデータ 平均 115.4152 回
5 個のデータ 平均 665.8918 回

予想通りですが、やはり運任せのためソートができるまでの回数はとんでもなく多いですね。

今回はこれでおしまいにします。それではまた次回。

Posted by 春日井 優