ALDS1_6 Quick Sortを解く話

情報系の学生ならみんな知っているクイックソートを解く．

自分は学部時代にやったはずだが，まったく覚えていなかった．

 

特徴

  • 配列を分割統治でソートするアルゴリズム
  • 配列を2つに分割する際におおまかにソート（Partitionアルゴリズム）
  • 分割した配列を引数にそれぞれ再帰的にQuicksortを呼び出し
  • 補助的な配列を必要としない（マージソートは必要）in-placeなアルゴリズム
  • Pivot（Partitionの閾値）の選び方によって様々な種類が存在．沼が深そうなので今回は配列の最後尾をPivotとするLomuto partition schemeを実装．

 

アルゴリズム

ALDS1_6-B Partitionを関数内で利用．

  1. Quicksort(A, l, r)
  2.     If l >= r
  3.         return
  4.     p = Partition(A, l, r)
  5.     Quicksort(A, l, p - 1)
  6.     Quicksort(A, p + 1, r)

 

 計算量

最悪ケースではPartitionに O(n) 必要．また，配列の要素数が n のときPartitionでの2分割は O(log_2(n)) 回実行. よって全体の計算量は O(nlog_2(n)).

 

実装

gistba1b8bbf64e8d297a504469b5b3f3c6b

 

感想

Partitionが理解できていれば問題なし．配列の最後尾をPivotとして選ぶのは今まで知らなかった．なんとなくクイックソートは真ん中で分割していくやつかー，とかずっと思ってた．