なにこれ
前回の続き
今回扱うのはソートです。
代表的なソートとして、マージソートとクイックソートをまとめます。
マージソート
「配列を半分に分割、分割された配列毎にソートして、合わせるときに先頭の値を比較する」ことを再帰的に行う
- n個の要素を毎回半分に分ける、それを要素が1個になるまで繰り返す
- すなわち深さがlog(n)の完全木ができあがり、各深さでマージをするので、マージソートの性能はO(nlogn)となる
クイックソート
「配列内のランダムな値(pivot)を選択、選択した値より大きい配列・小さい配列に分割し、分割された配列内でソートする」ことを再帰的に行う
