データのソート(並べ替え)について

データのソート(並べ替え)について

データのソート(並べ替え)はアルゴリズムの基本となる。ソートのアルゴリズムとしては以下に示すようなものがある。

隣接する値同士を比較し入れ替える作業を繰り返す「バブルソート」、ピポットと呼ばれる基準値を定めて、データ群を基準値以上と基準値未満の2つのグループに分ける作業を繰り返すことで要素の入れ替えを行う「クイックソート」、データを最小の単位(単一要素)まで分解し、最小の単位からソート、マージ(併合)を繰り返して要素を並び替える「マージソート」。

一番目以降の要素から最小値を見つけて一番目の要素と交換し、二番目以降の要素から最小値を見つけて二番目の要素と交換する作業を続けて要素を並び替える「選択ソート」、前から2個要素を取り出し、順番が逆なら並び替え、次に3個目を取り出し、　2個までの中の適切な場所に挿入する作業を続けて要素を並び替える「挿入ソート」。

「ヒープソート」は、元のデータを以下に示すような順序木に一旦変換し、変換した順序木の「子と親」を比較していき、親が子より小さければ親と子を交換するという手続きを全てのノードの組み合わせについて行うものとなる。

ヒープソートは消費するメモリも少なく高速で処理できるという特徴がある。

これらのアルゴリズム(特に最後の2分木)に関しては、より複雑なアルゴリズムのベースとなる。

Clojureのプログラムの中で単純にソートをしたい場合は以下のような形で行える。

user=> (sort [3 1 2 4])
(1 2 3 4)

user=> (sort > (vals {:foo 5, :bar 2, :baz 10}))
(10 5 2)

;; do not do this, use sort-by instead
user=> (sort #(compare (last %1) (last %2)) {:b 1 :c 3 :a  2})
([:b 1] [:a 2] [:c 3])

;; like this:
user=> (sort-by last {:b 1 :c 3 :a 2})
([:b 1] [:a 2] [:c 3])

基本的には「sort」関数を用いて、その後ろに>をつければ降順、なければ昇順、また最後のサンプル「sort-by」は特定の関数(last、マップデータの後の部分でソート)を用いたソートを示している。