「Pythonではじめるアルゴリズム入門」#03 - ソートアルゴリズム

「Pythonではじめるアルゴリズム入門」の学習記録です。学習に使ったファイルやコードなどをアップしていきます。
今回はソートに用いるアルゴリズムについて学びました。

https://www.amazon.co.jp/Python%E3%81%A7%E3%81%AF%E3%81%98%E3%82%81%E3%82%8B%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E5%85%A5%E9%96%80-%E4%BC%9D%E7%B5%B1%E7%9A%84%E3%81%AA%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A7%E5%AD%A6%E3%81%B6%E5%AE%9A%E7%9F%B3%E3%81%A8%E8%A8%88%E7%AE%97%E9%87%8F-%E5%A2%97%E4%BA%95-%E6%95%8F%E5%85%8B/dp/4798163236

# ソートに用いるアルゴリズム
リストを昇順・降順に並べ替える際の手法・計算量について考えます。
- 選択ソート
- 挿入ソート
- バブルソート
- ヒープソート
- マージソート
- クイックソート

# 選択ソート
リストの中から最小の値を見つけ、値をリストの先頭と交換します。計算量のオーダーは`O(n^2)`です。
```python
#先頭のインデックスから調べていき、徐々に後ろの方に範囲を狭める
#実際に何回処理が行われたかをいカウントする

data = [6,15,4,2,8,5,11,9,7,13]
calcurated = 0
print("ソート前：")
print(data)

for i in range(len(data)):
    min = i
    for j in range(i+1, len(data)):
        if data[min] > data[j]:
            min = j
            calcurated += 1

    data[i],data[min] = data[min], data[i]

print("ソート後：")
print(data)
print("処理回数：")
print(calcurated)
```
```python
ソート前：
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
ソート後：
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
処理回数：
11
```

# 挿入ソート
データを先頭から順に比較し、格納する位置を見つけて追加します。値はリストの一番後ろにまず格納し、１つずつリストの後ろから順にコピーしていくという方法でソートします。計算量のオーダーは`O(n^2)`です。
```python
#先頭のインデックスから調べていき、徐々に後ろの方に範囲を狭める
data = [6,15,4,2,8,5,11,9,7,13]
calcurated = 0
print("ソート前：")
print(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
        calcurated += 1

    data[j+1] = temp

print("ソート後：")
print(data)
print("処理回数：")
print(calcurated)
```
```python
ソート前：
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
ソート後：
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
処理回数：
17
```

# バブルソート
データが右側の方が小さければ左側と交換する、というタスクを繰り返します。最小の数が左端・最大の数が右端に行くまでタスクを繰り返すとソートが完了します。計算量のオーダーは`O(n^2)`です。
```python
#先頭のインデックスから調べていき、徐々に後ろの方に範囲を狭める
data = [6,15,4,2,8,5,11,9,7,13]
calcurated = 0
print("ソート前：")
print(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]
            calcurated += 1

print("ソート後：")
print(data)
print("処理回数：")
print(calcurated)
```
```python
ソート前：
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
ソート後：
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
処理回数：
17
```
# ヒープソート
ヒープは木構造のデータ構造で、子ノードの値は親ノードと比べ等しいか大きくなる、という条件を満たす木構造データです。
ヒープに要素を追加する場合、木構造の最後の部分に要素を追加します。
ヒープを使って値をソートするには、追加した要素と親ノードを比較し親ノードの方が小さければそれと交換する、というタスクを繰り返します。
ヒープを使ったソートの計算数は`O(n・logn)`となります。これはn個のノードがある木の高さが`log2(n)`であり、**計算数が2の対数に比例する**為です。選択ソートと比べると、データ量が多いときに処理能力が向上しますが、ヒープを作成する計算が必要となります。
```python
data = [6,15,4,2,8,5,11,9,7,13]
calcurated = 0

print("データのリスト：")
print(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

        calcurated +=1
print("ヒープ構造構成後：")
print(data)

#ヒープ構造になったリストをソートする
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
            calcurated +=1
        #右下>左下の場合
        else:
            #親ノードと交換
            data[j], data[2*j+2] = data[2*j+2], data[j]
            #探索するノードを右下に移動
            j = 2*j+2
            calcurated +=1

#ソートを実行する
print("ソート後：")
print(data)
print("処理回数：")
print(calcurated)
```
```python
データのリスト：
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
ヒープ構造構成後：
[15, 13, 11, 8, 9, 4, 5, 2, 7, 6]
ソート後：
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
処理回数：
18
```
# マージソート
ソートしたいデータを2分割するタスクを繰り返し、これらがバラバラになった状態からソートを開始します。n個リストを分割した際の段数は`log2(n)`となり、リストが結合されるまでの計算時間はヒープソートと同様`O(n・logn)`となります。
```python
data = [6,15,4,2,8,5,11,9,7,13]

print("データのリスト：")
print(data)

#マージソートを実行する為の関数
def merge_sort(data):
    #データが1つしかない→値をそのまま返す
    if len(data) <= 1:
        return data
    #リストの中央のインデックスを計算
    mid = len(data)//2
    #データの右側
    left=merge_sort(data[:mid])
    #データの右側
    right=merge_sort(data[mid:])
    #データを結合する
    return merge(left, right)

#データ結合を実行するための関数
def merge(left, right):
    result = []
    i,j = 0,0

    while (i<len(left)) and (j<len(right)):
        #左<＝右の時 - 返り値に左側のリストから取り出して追加
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        #右<＝左の時 - 返り値に右側のリストから取り出して追加
        else:
            result.append(right[j])
            j += 1

    #残りをまとめて追加する
    if i < len(left):
        result.extend(left[i:])
    if j < len(right):
        result.extend(right[j:])
    return result

print("ソート後：")
print(merge_sort(data))
```
```python
データのリスト：
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
ソート後：
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
```
# クイックソート
リストからデータを1つ選び、小さい要素と大きい要素に分割します。
分割の基準となる値はピボット(Pivot)といいます。このタスクを再帰的に繰り返し、データ数が1になるまで繰り返します。
```python
data = [6,15,4,2,8,5,11,9,7,13]

print("データのリスト：")
print(data)

#マージソートを実行する為の関数
def quick_sort(data):
    #データ数が1になるまで繰り返す
    if len(data) <= 1:
        return data

    #ピボットの値はデータの先頭とする
    pivot = data[0]
    left, right, same = [], [], 0

    for i in data:
        #値がピボットより小さい→左側のリストにアペンド
        if i < pivot:
            left.append(i)
        #値がピボットより大きい→右側のリストにアペンド
        elif i > pivot:
            right.append(i)
        else:
            same += 1
    #左側を再帰的にクイックソート
    left = quick_sort(left)
    #右側を再帰的にクイックソート
    right = quick_sort(right)

    #ソートされた値 + ピボットと一致した値
    return left + [pivot]*same + right

print("ソート後：")
print(quick_sort(data))
```
```python
データのリスト：
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
ソート後：
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
```

# Pythonのsortメソッド
ソートアルゴリズムは、たいていPythonのsortメソッドを使うと最も高速な処理を自動で行ってくれます。計算量をカウントする等でなければ、sortメソッドを使うと間違いないでしょう。
```python
#sortメソッドでソートする
data = [6,15,4,2,8,5,11,9,7,13]
calcurated = 0
print("ソート前：")
print(data)

data.sort()

print("ソート後：")
print(data)
```
```python
ソート前：
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
ソート後：
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
```

![スクリーンショット 2023-03-04 201647.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/337578/e619a78a-9a4a-b438-f2b4-6c8b84d142e8.png)
※（「Pythonではじめるアルゴリズム入門」より引用）