100日後にエンジニアになるキミ - 60日目 - プログラミング - データ構造とソートアルゴリズムについて

昨日までのはこちら

[100日後にエンジニアになるキミ - 59日目 - プログラミング - アルゴリズムについて](https://qiita.com/otupy/items/f1a5e81633b868f3b5ed)

[100日後にエンジニアになるキミ - 53日目 - Git - Gitについて](https://qiita.com/otupy/items/0abaad82a7f3fea73f1f)

[100日後にエンジニアになるキミ - 42日目 - クラウド - クラウドサービスについて](https://qiita.com/otupy/items/d1765f1541a104ed6133)

[100日後にエンジニアになるキミ - 36日目 - データベース - データベースについて](https://qiita.com/otupy/items/7af17635d576677606dc)

[100日後にエンジニアになるキミ - 24日目 - Python - Python言語の基礎1](https://qiita.com/otupy/items/6d1e5453f530e07b7aec)

[100日後にエンジニアになるキミ - 18日目 - Javascript - JavaScriptの基礎1](https://qiita.com/otupy/items/2f71d5f9c754b29d9555)

[100日後にエンジニアになるキミ - 14日目 - CSS - CSSの基礎1](https://qiita.com/otupy/items/61a97863f6df14171994)

[100日後にエンジニアになるキミ - 6日目 - HTML - HTMLの基礎1](https://qiita.com/otupy/items/cd2315dcb38671cfded0)

## データ構造

アルゴリズムを学ぶ上で重要なのがデータ構造です。
アルゴリズムは手順であるので、どのようなデータをどのように操作するのかと言った
データの構造もアルゴリズムでは重要な項目となります。

### リスト

Pythonのリスト型は配列形式のデータ型でインデックスを用いて
順番でアクセスすることができます。

リスト型では様々なデータを要素として格納することができ
要素の追加、変更、入れ替え、削除を行うことができます。

```python
# リストの定義
l = [1,2,3,4,5]
print(l)

# 要素の参照
print(l[0])

# 要素の変更
l[1] = 8
print(l)

# 要素の追加
l.append(6)
print(l)

# 要素の削除
l.pop(3)
print(l)

# 要素の挿入
l.insert(4,9)
print(l)

# 要素の入れ替え
l[0], l[3] = l[3], l[0]
print(l)
```
[1, 2, 3, 4, 5]
1
[1, 8, 3, 4, 5]
[1, 8, 3, 4, 5, 6]
[1, 8, 3, 5, 6]
[1, 8, 3, 5, 9, 6]
[5, 8, 3, 1, 9, 6]

### スタックとキュー

`スタック`も`キュー`もデータの取り扱い方法の１つになります。

**スタック**
・データ追加は列の先頭から、データ取り出しも列の先頭から
・後入れ先出しLIFO(Last-In-First-Out）
・スタックにデータを入れることを`プッシュ(push)`、取り出すことを`ポップ(pop)`と言う

![](https://upload.wikimedia.org/wikipedia/commons/thumb/b/b4/Lifo_stack.png/700px-Lifo_stack.png)


**キュー**
・データ追加は列の末尾、データの取り出しは列の先頭から
・先入れ先出し(トコロテン方式）FIFO (First-In-First-Out)
・キューにデータを入れることを`エンキュー(enqueue)`、取り出すことを`デキュー(dequeue)`という

![](https://upload.wikimedia.org/wikipedia/commons/thumb/5/52/Data_Queue.svg/480px-Data_Queue.svg.png)

参考：wikipedia

Pythonではリスト型やçで実現することができます。


**スタック**

```python
stack = []

# プッシュ
stack.append(1)
stack.append(2)
stack.append(3)
print(stack)

# ポップ
stack.pop()
print(stack)
stack.pop()
print(stack)
```
[1, 2, 3]
[1, 2]
[1]


**キュー**

```python
from collections import deque

# キューの定義
queue = deque(["A","B","C"])
print(queue)

# エンキュー
queue.append("D")
print(queue)

# デキュー
queue.popleft()
print(queue)
```
deque(['A', 'B', 'C'])
deque(['A', 'B', 'C', 'D'])
deque(['A', 'B', 'C'])

### ヒープ(heap)

ヒープとは子要素は親要素より常に大きいか等しい(または常に小さいか等しい)
という制約を持つ木構造のデータの事です。

単に`ヒープ`と言う場合二分木を使った`二分ヒープ`を指すことが多いです。

![](https://upload.wikimedia.org/wikipedia/commons/6/60/Binary_heap_indexing.png)

参考：wikipedia

ヒープはPythonではheapqライブラリで実現することができます。
ヒープでは最小値(もしくは最大値)を直ぐに取り出すことができます。

```python
import heapq

# リストを作成
heap = [1, 6, 8, 0, -1]
print(heap)

# 既存のリストをヒープ化(最小値)
heapq.heapify(heap)
print(heap)

# 要素を追加
heapq.heappush(heap, 10)
print(heap)

# 最小値を削除
print(heapq.heappop(heap))
print(heap)

max_heap = [3,7,5,9,-2]
print(max_heap)
# 最大値でヒープ作成
heapq._heapify_max(max_heap) 
print(max_heap)

# 最大値を削除
print(heapq._heappop_max(max_heap))
print(max_heap)
```
[1, 6, 8, 0, -1]
[-1, 0, 8, 1, 6]
[-1, 0, 8, 1, 6, 10]
-1
[0, 1, 8, 10, 6]
[3, 7, 5, 9, -2]
[9, 7, 5, 3, -2]
9
[7, 3, 5, -2]




## ソートアルゴリズムについて

`ソートアルゴリズム`は並び替えを行うアルゴリズムのことです。
単純に並び替えを行うにも様々なバリエーションがあります。

安定な`stable`並び替えとはデータ中に同一キーを持つレコードが複数ある場合
並べ替えた後に並べ替え前のレコードの順序関係が維持されます。

並べ替えることで並べ替え前の位置関係が崩れるような並べ替えを
不安定`unstable`な並べ替えといいます。

並べ替えが高速で終了し安定する並べ替えアルゴリズムの採用が望ましいです。

ソートアルゴリズムではその計算量なども1つの目安になります。
一般的に言われているソート アルゴリズムの計算量は以下の通りです。


| アルゴリズム | 安定性 | 平均時間 | 最悪時間 | 最良時間 | 最悪空間量 |
|:--:|:--:|:--:|:--:|:--:|:--:|
| バブルソート | 安定 | $\mathcal{O}(n^2)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(n)$ | $\mathcal{O}(1)$ |
| 選択ソート | 不安定 | $\mathcal{O}(n^2)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(n)$ | $\mathcal{O}(n)$ |
| 挿入ソート | 安定 | $\mathcal{O}(n^2)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(n)$ | $\mathcal{O}(n)$ |
| ヒープソート | 不安定 | $\mathcal{O}(n\log n)$ | $\mathcal{O}(n\log n)$ | $\mathcal{O}(n\log n)$ | $\mathcal{O}(1)$ |
| マージソート | 安定 | $\mathcal{O}(n\log n)$ | $\mathcal{O}(n\log n)$ | $\mathcal{O}(n\log n)$ | $\mathcal{O}(n)$ |
| クイックソート | 不安定 | $\mathcal{O}(n\log n)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(n)$ | $\mathcal{O}(n)$ |
| pythonソート(Timソート) | 安定 | $\mathcal{O}(n\log n)$ | $\mathcal{O}(n\log n)$ | $\mathcal{O}(n)$ | $\mathcal{O}(n)$ |

ここからは様々なソートアルゴリズムについて見ていきましょう。
実装例も載せていますが、もっと良い書き方があると思います。

### バブルソート(bubble sort)

`バブルソート`はリストにおいて隣り合うふたつの要素の値を比較して
条件に応じた交換を行う整列アルゴリズムです。

値の大きい順(降順)か値の小さい順(昇順)にリストを並び替えます。

```python
# バブルソート 
def bubble_sort(data):
    for i in range(len(data)):
        for j in range(len(data) - i - 1):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
    return data
```

### 選択ソート(select sort)

`選択ソート`は配列の最小値(最大値)を持つ要素を探して
それを配列の先頭要素と交換することで整列を行うアルゴリズムです。

```python
# 選択ソート
def select_sort(data):
    for i in range(len(data)):
        min = i
        for j in range(i + 1, len(data)):
            if data[min] > data[j]:
                min = j
        data[i], data[min] = data[min], data[i]
    return data
```


### 挿入ソート(insert sort)

`挿入ソート`はリストの整列済みの部分に対して新たな要素を適切な位置に挿入することで
整列を行うアルゴリズムです。

```python
# 挿入ソート
def insert_sort(data):
    for i in range(1, len(data)):
        temp = data[i]
        j = i - 1
        while (j >= 0) and (data[j] > temp):
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = temp
    return data
```


### ヒープソート(heap sort)

`ヒープソート`とはリストの並べ替えを`二分ヒープ木を`用いて行うソートのアルゴリズムです。

未整列のリストから要素を取り出し、順にヒープに追加する。
すべての要素を追加するまで次の操作を繰り返す(ルートを取り出し整列済みリストに追加する)

```python
# ヒープソート
def heap_sort(data):
    for i in range(len(data)):
        j = i
        while (j > 0) and (data[(j - 1) // 2] < data[j]):
            data[(j - 1) // 2], data[j] = data[j], data[(j - 1) // 2]
            j = (j - 1) // 2

    for i in range(len(data), 0, -1):
        data[i - 1], data[0] = data[0], data[i - 1]
        j = 0
        while ((2 * j + 1 < i - 1) and (data[j] < data[2 * j + 1]))\
            or ((2 * j + 2 < i - 1) and (data[j] < data[2 * j + 2])):
            if (2 * j + 2 == i - 1) or (data[2 * j + 1] > data[2 * j + 2]):
                data[j], data[2 * j + 1] = data[2 * j + 1], data[j]
                j = 2 * j + 1
            else:
                data[j], data[2 * j + 2] = data[2 * j + 2], data[j]
                j = 2 * j + 2
    return data
```

pythonではヒープキューを実現するライブラリheapqを用いて
簡易にヒープソート を書くこともできます。

```python
import heapq

# heapqを用いたヒープソート 
def heap_sort2(data):
    h = data.copy()
    heapq.heapify(h)
    return [heapq.heappop(h) for _ in range(len(h))]
```

### マージソート(merge sort)

`マージソート`は並べ替えたい配列を再帰的に分割していき、再び併合`マージ`し
並び替えを実現しようとするソートアルゴリズムです。

```python
# マージソート
def merge_sort(data):
    if len(data) <= 1:
        return data
    m = len(data) // 2
    l = merge_sort(data[:m])
    r = merge_sort(data[m:])
    return merge(l , r)

def merge(left, right):
    res , i , j = [], 0, 0
    while (i < len(left)) and (j < len(right)):
        if left[i] <= right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    if i < len(left):
        res.extend(left[i:])
    if j < len(right):
        res.extend(right[j:])
    return res
```


### クイックソート(quick sort)

`クイックソート`はデータの比較と交換回数が非常に少ないのが特徴で
ランダムに散らばっているデータに対して、効率良く並べ替えを実現できますが
安定はしないアルゴリズムです。

```python
def quick_sort(data):
    def quick(list, left, right):
        pl = left
        pr = right
        y = list[(pl + pr) // 2]
        while True:
            while list[pl] < y: pl += 1
            while list[pr] > y: pr -= 1
            if pl <= pr:
                list[pl], list[pr] = list[pr], list[pl]
                pl += 1
                pr -= 1
            if pl > pr:
                break
        if left < pr: quick(list, left, pr)
        if pl < right: quick(list, pl, right)
        return data
    quick(data, 0, len(data) - 1)
    return data
```


### Pythonの標準ソート(sort)

Pythonの標準ソートは(恐らくは)`Timsort`です。

`Timsort`は`マージソート`と`挿入ソート`から派生したハイブリッドの安定した
ソートアルゴリズムでさまざまな種類のデータで適切に機能するように設計されています。

```python
def python_sort(data):
    data.sort()
    return data
```

### ソートアルゴリズムの実行時間比べ

上記のソートアルゴリズムの実行時間を測ってみましょう。
下記のようなコードで簡易に測ります。

10000個の数値の並び替えを行います。
`jupyter notebook`であれば`%time`を用いると時間を測ることができます。

```python
import numpy as np
import sys
sys.setrecursionlimit(20000)

data = np.arange(10000)
np.random.shuffle(data)
data = list(data)

print('bubble_sort')
%time l = bubble_sort(data)
print('select_sort')
%time l = select_sort(data)
print('insert_sort')
%time l = insert_sort(data)
print('heap_sort')
%time l = heap_sort(data)
print('heap_sort2')
%time l = heap_sort2(data)
print('merge_sort')
%time l = merge_sort(data)
print('quick_sort')
%time l = quick_sort(data)
print('python_sort')
%time l = python_sort(data)
```
bubble_sort
CPU times: user 18 µs, sys: 0 ns, total: 18 µs
Wall time: 20 µs
select_sort
CPU times: user 18 µs, sys: 1 µs, total: 19 µs
Wall time: 21 µs
insert_sort
CPU times: user 7 µs, sys: 0 ns, total: 7 µs
Wall time: 10 µs
heap_sort
CPU times: user 38 µs, sys: 1 µs, total: 39 µs
Wall time: 40.1 µs
heap_sort2
CPU times: user 11 µs, sys: 0 ns, total: 11 µs
Wall time: 12.9 µs
merge_sort
CPU times: user 31 µs, sys: 1e+03 ns, total: 32 µs
Wall time: 33.1 µs
quick_sort
CPU times: user 13 µs, sys: 1 µs, total: 14 µs
Wall time: 14.8 µs
python_sort
CPU times: user 4 µs, sys: 0 ns, total: 4 µs
Wall time: 6.2 µs

さて時間が一番短いのはPythonの標準ソートですね。

ここらへんは実装の仕方次第でもかなり変わると思いますが
標準ソートを超える速さを実現するのはかなり至難だと思いますので
通常はソートに関しては自前でプログラムを書く必要はないかと思います。

## まとめ

Pythonのソートは非常に高性能なのであまり普段は気にしていないかもしれませんが
ソートで困ることは少ないです。

どういった仕組みでソートが行われているのか
それぞれの手法でどう違っているのかを見比べてみると
アルゴリズムの奥深さが分かってくると思います。

君がエンジニアになるまであと40日

## 作者の情報
乙pyのHP：
http://www.otupy.net/

Youtube：
https://www.youtube.com/channel/UCaT7xpeq8n1G_HcJKKSOXMw

Twitter：
https://twitter.com/otupython