今からお前んちこいよ

多摩川沿いにて細々とお勉強。

Wikipedia - Sorting algorithm を舐めるな!?

技術書とまではいかないけど、
Wikipedia - Sorting algorithm がまじ最高だった。

いろんなアルゴリズム本がある中、
wikiはソートアルゴリズムの全体像を把握するのにすごくよかった。
個人的にチートシートとしてまとめる。

安定なソートとは

(引用)

if one came before the other in the input, it will also come before the other in the output.

(オレオレ訳)

ある値が(同等な)他の値の前にあるインプットを、ある値が他の値の前にある状態で出力する

⇒ 同値を含むインプットを、その順序を崩さずに出力するソート。

アルゴリズムの比較表

主要

Name Best Ave Worst Memory Stable Method
Quicksort nlogn nlogn n2 *1 *2 Partitioning
Merge sort nlogn nlogn nlogn n Yes Merging
Heapsort nlogn nlogn nlogn 1 No Selection
Insertion sort n n2 n2 1 Yes Insertion
Selection sort n2 n2 n2 1 No Selection
Bubble sort n n2 n2 1 Yes Exchanging
Binary tree sort nlogn nlogn nlogn n Yes Insertion

1) 平均は logn, worst-caseのメモリ使用量はn
2) 基本的には in-place ソートは不安定となるが、安定バージョンも存在する。

複合型

Name Best Average Worst Memory Stable Method
Introsort nlogn nlogn nlogn logn No Partitioning & Selection
Timsort n nlogn nlogn n Yes Insertion & Merging

 

よく使われるソートアルゴリズム

(引用)

Insertion sort is widely used for small data sets, while for large data sets an asymptotically efficient sort is used, primarily heap sort, merge sort, or quicksort. Efficient implementations generally use a hybrid algorithm, combining an asymptotically efficient algorithm for the overall sort with insertion sort for small lists at the bottom of a recursion.

(オレオレ訳)

挿入ソートは小さなデータセットに対して広く利用され、大きなデータセットでの効率的なソートには主に、ヒープソート、マージソート、クイックソートが利用される。効率化が進むと仕組みは徐々に複合型アルゴリズムとなり、再帰的な処理内で小さなリストに対して挿入ソートを利用するものもある。

(引用)

Highly tuned implementations use more sophisticated variants, such as Timsort (merge sort, insertion sort, and additional logic), used in Android, Java, and Python, and introsort (quicksort and heap sort), used (in variant forms) in some C++ sort implementations and in .NET.

(オレオレ訳)

さらに効率化されたものには、主にAndroidやJava、Pythonで利用されているティムソート(マージソート、挿入ソートなどの複合ロジック)や、C++のソートや.NETで利用されているイントロソート(クイックソートとヒープソートの複合)などがある。

 
へー(゜-゜)