Pythonに

こんばんは、ダンです。

Pythonのrandomクラスに面白いメソッドがあったからちょっとやってみた。

その名も！

random.shuffle()!!!

これは

random.shuffle([1,2,3])
と、実行すると

1,2,3の順番が並び変わると言うメソッドらしいです。

あれだよね。

こういうの見たらボゴソート作りたくなるよね。

ってわけで作ってみた。

import random

def bogo(s):
  while 1:
    num = s[0]
    f = True
    for x in s:
      if num <= x:
        num = x
      else:
        f = False
        break
    if f:
      return s
    random.shuffle(s)

print bogo([1,2,3,4,5,6,7,8,9,10])

やばいよ！このソート！
このリストをソートするにはO(n)だよ！！

このリストをクイックソートでやったらO(n^2)かかるからね・・！

---追記---

ボゴソートだけじゃつまらないからクイックソートも作ってみた！

def quick(s):
  if len(s) <= 1:
    return s
  mid = s[0]
  left = []
  right = []
  for x in s[1:]:
    if x <= mid:
      left.append(x)
    else:
      right.append(x)
  left = quick(left)
  right = quick(right)
  
  return left+[mid]+right

print quick([2,5,1,6,1,3,72,3,6])

うん、こんな感じかなっ

QuickSortはアルゴリズムは知ってたけど、実際に書いてみるのは初めて。

再帰関数ってオーダー求めにくいけど・・・

O(nlog(n))です！だって有名だもん！

次はマージソートかこうっかなー。