夕蛙のなく頃に

データアナリストとして学んだことや趣味で勉強し始めたIoTをアウトプットする

OpenDataStructures第11章を自分用にまとめる(ソート)

なにこれ

前回の続き

blog.frogdusk.com

今回扱うのはソートです。
代表的なソートとして、マージソートクイックソートをまとめます。

マージソート

「配列を半分に分割、分割された配列毎にソートして、合わせるときに先頭の値を比較する」ことを再帰的に行う

f:id:frogdusk:20190726180245p:plain

  • n個の要素を毎回半分に分ける、それを要素が1個になるまで繰り返す
  • すなわち深さがlog(n)の完全木ができあがり、各深さでマージをするので、マージソートの性能はO(nlogn)となる

クイックソート

「配列内のランダムな値(pivot)を選択、選択した値より大きい配列・小さい配列に分割し、分割された配列内でソートする」ことを再帰的に行う

f:id:frogdusk:20190726180301p:plain

  • 各要素同士が比較される回数の期待値から各要素同士ということで積分すると、全体で比較される回数合計値の期待値がわかる
  • クイックソートの性能はO(nlogn)となる