ALDS1_6-B Partitionを解く話

クイックソートで使うPartitionを実装する．

特徴

・閾値以下か，それより大きかで配列を分割するアルゴリズム．

・閾値で分けるだけなので全体はソートされない．

アルゴリズム

1. Partition(A, l, r)
2. threshold = A[r]
3. i = l - 1
4. for j = l to r - 1
5.     if A[j] <= threshold
6.         i = i + 1
7.         exchange(A[j], A[i])
8. i++
9. exchange(A[i], A[r])
10. return i

計算量

最悪ケースではjが増えるたびに交換するので .

実装

gist6642213dcdfec5d8dbf6d23f0436e01b

感想

とにかくクイックソートのために必要なアルゴリズムという印象．

クイックソートで使用するときは最後にi + 1を閾値の位置として返す．