【Python】クイックソートを実装してみた

Pythonでクイックソートを実装してみました。

クイックソートは、分割統治法(divide-and-conquar)を使い一度分割し再度合体させることで高速なソートを実現します。

  1. 要素が1以下なら処理を行わない
  2. リストの1番左の値をピボットとして選択
  3. ピボット以下をサブリストleft,ピボットよりも大きい値をサブリストrightに分割する
  4. 分割した2つのサブリストに再帰的にソートを適用する
  5. 分割した2つのサブリストとピボットを合体して終了

具体的に流れを見ていきます。

1. 整列前のリストです。
[3, 9, 6, 1, 2] 

2. 1番左の値をピボットに選択
pivot 3 

3. サブリストrightを作成、クイックソートを適用し整列する
[9, 6]

4. サブリストleftを作成、クイックソートを適用し整列する
[1, 2]

5. 最後にleft,pivot,rightを合成して完成!
[1, 2, 3, 6, 9]

コード例は以下の通り。

def QuickSort(num_list):
  
  n = len(num_list)
  
  if n <= 1:
    return num_list
  
  pivot = num_list[0]
  
  right=[]
  left=[]
  
  for i in range(1,n):
    if num_list[i] <= pivot:
      left.append(num_list[i])
    else:
      right.append(num_list[i])
  
  
  r = QuickSort(right)
  l = QuickSort(left)
  
  return l+[pivot]+r

おわり。

3 件のコメント

  • こんにちは
    突然申し訳ないのですが、実装したクイックソートのnum_listに実際に数字を入れて、並び替えたものをprintで表示するにはどうしたら良いのかご教授頂けると幸いです。

  • のっくん へ返信する コメントをキャンセル

    メールアドレスが公開されることはありません。 が付いている欄は必須項目です

    ABOUTこの記事をかいた人

    個人アプリ開発者。Python、Swift、Unityのことを発信します。月間2.5万PVブログ運営。 Twitter:@yamagablog