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]
できてますね!
ちなみにクイックソートの計算量をさっと解いてみた(?)
できてるかは不安であるが。
まさか授業以外で漸化式を解くとは。
まぁこんな感じです。
最悪の場合はO(n^2)ですね。
今日も30分チャレンジOKです。
以上です。