基本的なソートアルゴリズムまとめて可視化GIFで解説

# 0、ソート概要

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

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

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

|           |              |                             |
|-----------|--------------|-----------------------------|
|比較ソート　|Exchange sort |Bubble Sort<br>Quick Sort    |
|　　　　　　|Insertion Sort|Insertion Sort<br>Shell Sort |
|　　　　　　|Selection Sort|Selection Sort<br>Heap Sort  |
|　　　　　　|Merge Sort    |Two-way merge sort<br>Multi-way merge sort|
|           |              ||
|非比较ソート|Counting Sort ||
|　　　　　　|Bucket Sort   ||
|　　　　　　|Radix Sort    ||

## 0.2 アルゴリズムの複雑さ

|名称           |平均計算時間          |最悪計算時間         |最良計算時間         |メモリ使用量       |安定性  |手法 |備考|
|---|---|---|---|---|---|---|---|
|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)$$       | $$○$$  |$$☓$$||

## 0.3 関連する概念

* 安定：同等なデータのソート前の順序が、ソート後も保存されるものをいう。つまり、ソート途中の各状態において、常に順位の位置関係を保っていることをいう。
* 時間計算量：問題を解く際に必要とする手順の回数。これが少ないほど、より短い時間で問題を解くことができる。
* 空間計算量：問題を解く際に必要とする記憶領域の容量。これが少ないほど、より少ないメモリ容量で問題を解くことができる。

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

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

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

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

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

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

## [1、バブルソート（Bubble Sort）](https://qiita.com/yp2211/items/4c3e08cc5247e5165bdf)
## [2、選択ソート（Selection Sort）](https://qiita.com/yp2211/items/8fbd8404466998420374)
## [3、挿入ソート（Insertion Sort）](https://qiita.com/yp2211/items/d18b514efaaae64c74c1)
## [4、希尔排序（Shell Sort）](https://qiita.com/yp2211/items/3ed2c82e587aab4a2020)
## [5、マージソート（Merge Sort）](https://qiita.com/yp2211/items/db34480c64249ddd41e5)
## [6、クイックソート （Quick Sort）](https://qiita.com/yp2211/items/14caebec72da26e75760)
## [7、ヒープソート （Heap Sort）](https://qiita.com/yp2211/items/47a5f1a2e9fdee966529)
## [8、カウントソート（Counting Sort）](https://qiita.com/yp2211/items/a929595ba233d2bc581a)
## [9、バケットソート（Bucket Sort）](https://qiita.com/yp2211/items/1efe5b6a12f85055bd9a)
## [10、基数ソート（Radix Sort）](https://qiita.com/yp2211/items/683fa423b3f40a871064)


* * *