python2.7

クイックソート

More than 1 year has passed since last update.

同じく書籍より


#クイックソート
def quicksort(array):
if len(array) < 2:
return array #基本ケース 配列に1個だけならなれべ変えることができない
else:
pivot = array[0] #0番目をピボットとしてとる

#ピボットよりも小さい要素を全て含んだ部分配列
less = [i for i in array[1:] if i <= pivot] #配列1(2番目)以降が pivotより小さい場合less

#ピボットよりも大きい要素を全て含んだ部分配列
greater = [i for i in array[1:] if i > pivot] #配列1(2番目)以降が pivotより大きい場合less

return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([10,5,2,3])


[2,3,5,10]とちゃんと並べ替えられた

pivotを基準に小さいか大きいかでソートされているがreturn で再帰関数を使っている