【Python】クイックソート【アルゴリズム】

クイックソートについて
1. 概要
2. ソートの流れ
コード
1. [1]：要素数が1以下の場合はそのまま返す
2. [2]：分割されたリスト群を結合
参考

クイックソートについて

概要

分割統治法に分類される
計算量はO(nlogn)〜O(n^2)
計算量はピボットの選択により変動する
ちょうど半分になるような値をピボットとして選ぶと効率が良い
他のソートアルゴリズムと組み合わせて用いられる
並列処理が可能

ソートの流れ

リストの中から要素を1つ選ぶ
その値より大きいものと小さいリストに分割する
分割されたそれぞれのリストに対して、同様の処理を再帰的に行う
これ以上分割できない段階まで分割したリスト群を結合するとソート済みの結果を得られる

コード

data = [3,5,6,1,8,2,10,4,7,9]

def quick_sort(data):                #[1]要素数が1以下の場合そのまま返す
  if len(data)<=1:           
    return data
  
  pivot = data[0]                    #先頭の要素をピボットに指定
  left,right,same=[],[],0            #分割用のリストとピボットと同じ値の数を保存する変数を準備
  
  for i in data:                     #リストの要素数だけ繰り返す
    if i < pivot:                    #i番目の要素がピボットよりも小さい場合
      left.append(i)                 #leftに格納
    elif i > pivot:                  #i番目の要素がピボットよりも大きい場合
      right.append(i)                #rightに格納
    else:                            #ピボットと同値の場合
      same += 1                      #sameに1を加える
  left = quick_sort(left)            #ピボットよりも小さい数が保存されたリストであるleftに対して同様の処理を行う
  right = quick_sort(right)          #ピボットよりも大きい数が保存されたリストであるrightに対して同様の処理を行う
  return left + [pivot]*same +right  #[2]分割されたリスト群を結合

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

data = [3,5,6,1,8,2,10,4,7,9]

def quick_sort(data): #[1]要素数が1以下の場合そのまま返す

if len(data)<=1:

return data

pivot = data[0] #先頭の要素をピボットに指定

left,right,same=[],[],0 #分割用のリストとピボットと同じ値の数を保存する変数を準備

for i in data: #リストの要素数だけ繰り返す

if i < pivot: #i番目の要素がピボットよりも小さい場合

left.append(i) #leftに格納

elif i > pivot: #i番目の要素がピボットよりも大きい場合

right.append(i) #rightに格納

else: #ピボットと同値の場合

same += 1 #sameに1を加える

left = quick_sort(left) #ピボットよりも小さい数が保存されたリストであるleftに対して同様の処理を行う

right = quick_sort(right) #ピボットよりも大きい数が保存されたリストであるrightに対して同様の処理を行う

return left + [pivot]*same +right #[2]分割されたリスト群を結合

print(quick_sort(data))

#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

[1]：要素数が1以下の場合はそのまま返す

分割を繰り返していくと、最後は全てのリストの要素数が1になります。

[2]：分割されたリスト群を結合

[pivot]*sameについて、ピボットと同じ値がいくつあったかがsameに保存されています。

sameの数だけ掛け算して結合しています。

leftはピボットよりも小さい値が、rightはピボットよりも大きい値が分割されて格納されています。

そのため、left+ピボット+rightとすることで左から小さい順(昇順)にソートすることができます。

参考

こちらの書籍を用いて学習しています。

ピボットでの分割処理について、書籍の中ではリストの内包表記を用いてよりシンプルな実装方法が紹介されています。

コードを書くとき、人それぞれによく使っているライブラリや書き方があると思います。

他の方が書いたコードを読む時に自分が使ったことのないライブラリや書き方だと、非常に読みにくいと感じますが、

普段が自分が使わないものや書き方をなるべくたくさん読んだり取り入れることで、少しでもコードを読むスピードが上がるのではないかと思います。