読者です 読者をやめる 読者になる 読者になる

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として選ぶのは今まで知らなかった.なんとなくクイックソートは真ん中で分割していくやつかー,とかずっと思ってた.