kazumalab tech log

流行りとリラックマと嵐が大好きです。技術的ログ。

30分チャレンジ〜2日目〜

kazuma.です。

今日の30分チャレンジ結果です。

昨日は悔しい思いをしました。(csvで死ぬという)


今日はそんなことをやってたらキリがないことに気づき、今日はコードに配列をぶっこみました。
そんなこんなで今日は昨日解けなかったクイックソートを解いてみました。(悔しかった)

print "First >> ",
a = [3,5,7,4,2,8,9]
print a
def quicksort(seq):
    if len(seq) < 1:
        return seq
    pivot = seq[0]
    num = len(seq)
    low = []
    high =[]
    for i in range(1,num):
        if pivot > seq[i]:
            low.append(seq[i])
        if pivot < seq[i]:
            high.append(seq[i])
    low = quicksort(low)
    high = quicksort(high)
    center = [pivot]
    return low + center +high

a = [3,5,7,4,2,8,9]
a = quicksort(a)

print "Sorting >> ",
print a

今回は30分で解きれました。

出力結果をみてみます。

# python quick.py
First >>  [3, 5, 7, 4, 2, 8, 9]
Sorting >>  [2, 3, 4, 5, 7, 8, 9]

できてますね!

ちなみにクイックソートの計算量をさっと解いてみた(?)
できてるかは不安であるが。
f:id:kazumalab:20150707234313p:plain

まさか授業以外で漸化式を解くとは。


まぁこんな感じです。

最悪の場合はO(n^2)ですね。

今日も30分チャレンジOKです。

以上です。