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

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が増えるたびに交換するので  O(n).

 

実装

gist6642213dcdfec5d8dbf6d23f0436e01b

 

感想

とにかくクイックソートのために必要なアルゴリズムという印象.
クイックソートで使用するときは最後にi + 1を閾値の位置として返す.