ソート - bbr-program-memo

ソート

Sort

何らかの順序に従い、データを並べ替えること

ソートはかなりコストが高い処理。やらなくて済むならその方がよい。

ソートを全体処理として行う方法と、データの追加ごとに処理する方法とがある。データの性質によって使い分ける。

マップやセットではコレクション自体がソート済みになっていることがある。(その方が検索が容易なため)

原理的には最も高速になるのはクイックソートになる。

要素数がとても少ない場合、また、ソート済みデータに対してのクイックソートは効率が悪い。

これを改善するために複数のソートを組み合わせるのが一般的な実装。

一度ソートしておけば、二分探索ができるようになる。

最近はマルチスレッドで並列的にソートをするものがある。