並び替え(ソート)

sort.png

基礎知識

適切なソーティングアルゴリズムの選び方を左右する条件

  • ソートすべきデータの個数
  • データが既にソートされている程度
  • データが取りうる値の範囲
それを踏まえた上で、まとめ!
最悪計算量 消費メモリ
挿入ソート
バブルソート O(n2) O(1)
選択ソート O(n2) O(1)
マージソート O(n log(n) O(1) or O(n)
クイックソート O(n log(n)~O(n2) O(log(n))
基数ソート O(n log(n))~O(kn)

並べ替え用語

  • キー…ソートしたいと思っている数値のこと

複数の条件でソートしたい!など任意の比較を使ってソートする方法

自作クラスを作って、ソート用の関数をオーバーロードすれば、一つの条件でだけソートできることはわかった。
しかし、違う条件でもソートしたい場合はどうやって実装すればいい??
util.Collectionsに以下のような関数がある
java.util.Comparator) void sort(List<T> list, Comparator<? super T> c) 指定されたコンパレータが示す順序に従って、指定されたリストをソートします。

さて、これをどうやって使えばよいのか?

  1. 自分で、ソートの基準の役割をするComparatorインタフェースをimplementしたクラスを作る。
  2. compare()関数の中身を自分の好きなように書く
  3. そいつを引数として渡す


competition container

サポートサイト Wikidot.com competitioncontainer