はじめに
バブルソートなどのアルゴリズムを学ぼうと思ったので、手始めにランダムなFizzBuzz列をソートしてみた。
対象のランダムなFizzBuzz列を作成する。
数値をFizzBuzzに適宜変える関数fzbz()と、それをランダムな順番に変更するmake_random_fizzbuzz()とを定義してみた。
def fzbz(n):
if (n%15) == 0:
return "FizzBuzz"
elif (n%5) == 0:
return "Buzz"
elif (n%3) == 0:
return "Fizz"
else:
return n
import random
def make_random_fizzbuzz(start=1,finish=100):
seq = range(start,finish+1)
random_fizzbuzz = []
while seq:
random_fizzbuzz.append(fzbz(seq.pop(random.randint(0,len(seq)-1))))
return random_fizzbuzz
より具体的には、以下のような感じのリストをFizzBuzz的にソートしてみることを本記事の解決課題とする。
（上記関数により作成したリスト）
そもそもバブルソートとは（他サイトから引用）
バブルソートはリストにおいて基点となる要素とそれ以外の要素の値を比較して条件に応じた交換を行う整列アルゴリズムです。
条件とは値の大小関係です。「値の大きい順(降順)」か「値の小さい順(昇順)」にリストを並び替えます。
このソートを実行すると値の大きいまたは小さい要素が浮かびあがってくるように見えることから、バブル(bubble: 泡)ソートと呼ばれます。
アルゴリズム分析
リストを昇順に整列させる手順。
リストから要素をひとつ取り出す - 基点となる要素'A'
要素'A'と次の要素'B'の値を比較する
要素'A'が要素'B'より大きいなら、要素'A'と要素'B'の値を交換する
要素'A'と要素'C'、要素'A'と要素'D'のように各要素との比較/交換をリストの終端まで行う
リスト中で最も大きい値を持つ要素または小さい要素が基点となった位置へ浮かびあがる
基点となる要素を次へ進めて(要素'B')リストの終端まで手順2〜6を繰り返す
以上のように総当たりで比較を行い、条件に一致する交換を実行することで整列が完了します。
http://www.codereading.com/algo_and_ds/algo/bubble_sort.html
若干上記とは異なるかもしれないが、おそらく本質は同じなバブルソートをpythonで書いてみた。
まずはランダムな数列を生成する関数。
import random
def make_randoms(start=1,finish=100):
seq = range(start,finish+1)
randoms = []
while seq:
randoms.append(seq.pop(random.randint(0,len(seq)-1)))
return randoms
上記関数が作成した数列をソートする、存在意義がよくわからない関数。
def bubble_sort(target):
limit = len(target)-1
while limit > 0:
i = 0
while i<limit:
if target[i]>target[i+1]:
target[i], target[i+1] = target[i+1], target[i]
i += 1
limit -= 1
return target
修正すべき点
ランダムなFizzBuzz列で問題となるのは大小関係と思われる。
if target[i]>target[i+1]:
つまり、大小判定をしているこの辺をなんとかすればいいっぽい。
修正概要
そこで、文字列Fizz,Buzz,FizzBuzzを数値化するためのカウンタf,b,fbを定義するコードと、
(f,b,fb) = (3,5,15)
カウンタをもとにFizz,Buzz,FizzBuzzを数値化する関数と、
def zbzf(n,f,b,fb):
n = str(n)
if n == 'FizzBuzz':
return fb
elif n == 'Buzz':
return b
elif n == "Fizz":
return f
else:
return int(n)
Fizz,Buzz,FizzBuzzが登場した時にカウンタを更新する関数と
def next_count(n,f,b,fb):
if n == 'FizzBuzz':
fb += 15
elif n == 'Buzz':
if (b%15) == 10:
b += 10
else:
b += 5
elif n == "Fizz":
if (f%15) == 12:
f += 6
else:
f += 3
return f, b, fb
を作り、これらを使って各要素を比較、カウンタを更新するようにしてみた。
(f,b,fb) = (3,5,15)
while i<limit:
if zbzf(target[i],f,b,fb)>zbzf(target[i+1],f,b,fb):
target[i], target[i+1] = target[i+1], target[i]
f,b,fb = next_count(target[i],f,b,fb)
コード
import random
def fzbz(n):
if (n%15) == 0:
return "FizzBuzz"
elif (n%5) == 0:
return "Buzz"
elif (n%3) == 0:
return "Fizz"
else:
return n
def zbzf(n,f,b,fb):
n = str(n)
if n == 'FizzBuzz':
return fb
elif n == 'Buzz':
return b
elif n == "Fizz":
return f
else:
return int(n)
def make_random_fizzbuzz(start=1,finish=100):
seq = range(start,finish+1)
random_fizzbuzz = []
while seq:
random_fizzbuzz.append(fzbz(seq.pop(random.randint(0,len(seq)-1))))
return random_fizzbuzz
def next_count(n,f,b,fb):
if n == 'FizzBuzz':
fb += 15
elif n == 'Buzz':
if (b%15) == 10:
b += 10
else:
b += 5
elif n == "Fizz":
if (f%15) == 12:
f += 6
else:
f += 3
return f, b, fb
def fizzbuzz_sort(target):
limit = len(target)-1
while limit > 0:
i = 0
(f,b,fb) = (3,5,15)
while i<limit:
if zbzf(target[i],f,b,fb)>zbzf(target[i+1],f,b,fb):
target[i], target[i+1] = target[i+1], target[i]
f,b,fb = next_count(target[i],f,b,fb)
i += 1
limit -= 1
return target
print fizzbuzz_sort(make_random_fizzbuzz())
結果
ランダムだったFizzBuzzがソートされた！！
