0、ソート概要

0.1 ソートアルゴリズム分類

基本的なソートアルゴリズムは、次の2つのカテゴリに分類られます。

比较ソート：要素間の相対的な順序は比較によって決定されます。その時間計算量はO（nlogn）を超えることができないため、非線形時間比較ソートとも呼ばれます。
非比较ソート：要素間の相対的な順序は比較によって決定されません。比較ソートに基づいて時間の下限を突破し、線形時間で実行される可能性があるため、線形時間非比較ソートとも呼ばれます。


比較ソート	Exchange sort	Bubble Sort Quick Sort
	Insertion Sort	Insertion Sort Shell Sort
	Selection Sort	Selection Sort Heap Sort
	Merge Sort	Two-way merge sort Multi-way merge sort

非比较ソート	Counting Sort
	Bucket Sort
	Radix Sort

名称	平均計算時間	最悪計算時間	最良計算時間	メモリ使用量	安定性	手法
Insertion Sort	$$ O(n^2) $$	$$ O(n²) $$	$$ O(n) $$	$$O(1)$$	$$○$$	挿入
Shell Sort	$$ O(n^{1.3}) $$	$$ O(n^2) $$	$$ O(n) $$	$$O(1)$$	$$☓$$	挿入
Selection Sort	$$ O(n^2) $$	$$ O(n^2) $$	$$ O(n^2) $$	$$O(1)$$	$$☓$$	選択
Heap Sort	$$ O(nlog_{2}n) $$	$$ O(nlog_{2}n) $$	$$ O(nlog_{2}n) $$	$$O(1)$$	$$☓$$	選択
Bubble Sort	$$ O(n^2) $$	$$ O(n²) $$	$$ O(n) $$	$$O(1)$$	$$○$$	交換
Quick Sort	$$ O(nlog_{2}n) $$	$$ O(n²) $$	$$ O(nlog_{2}n) $$	$$O(nlog_{2}n)$$	$$☓$$	パーティショニング
Merge Sort	$$ O(nlog_{2}n) $$	$$ O(nlog_{2}n) $$	$$ O(nlog_{2}n) $$	$$O(n)$$	$$○$$	マージ

名称	平均計算時間	最悪計算時間	最良計算時間	メモリ使用量	安定性	$$n<<2^k?$$
Counting Sort	$$ O(n+k) $$	$$ O(n+k) $$	$$ O(n+k) $$	$$O(n+k)$$	$$○$$	$$☓$$
Bucket Sort	$$ O(n+k) $$	$$ O(n^2) $$	$$ O(n) $$	$$O(n+k)$$	$$○$$	$$☓$$
Radix Sort	$$ O(n*k) $$	$$ O(n*k) $$	$$ O(n*k) $$	$$O(n+k)$$	$$○$$	$$☓$$

一般的なクイックソート、マージソート、ヒープソート、バブルソートなどは比較ソートに属します。並べ替えの最終結果では、要素の順序は要素間の比較によって異なります。それぞれの番号は、それ自体の位置を決定するために他の番号と比較する必要があります。

バブルソートなどのソートでは、問題のサイズはnであり、n回比較する必要があるため、平均時間計算量はO（n²）です。マージソートやクイックソートなどのソートでは、分割統治法により問題サイズがlogN倍に削減されるため、平均時間計算量はO（nlogn）になります。

比較ソートの利点は、すべてのサイズのデータに適用でき、データの分布に関係なくソートできることです。比較ソートは、ソートが必要なすべての状況に適用できると言えます。

カウントソート、カーディナルソート、およびバケットソートは非比較ソートです。非比較ソートとは、各要素の前に必要な要素の数を決定することによるソートです。配列arrの場合、arr [i]の前にある要素の数を計算します。これにより、並べ替えられた配列内のarr [i]の位置が一意に決定されます。

非比較ソートでは、各要素の前にある既存の要素の数を決定するだけでよく、1回のトラバーサルですべてを解決できます。アルゴリズムの時間計算量はO（n）です。

非比較ソートの時間計算量は最も低くなりますが、非比較ソートでは一意の位置を決定するためのスペースが必要になるためです。したがって、データのスケールとデータの分散には特定の要件があります。