【Python】探索アルゴリズム・ソートの一例【基礎】

なんとなく頭の体操になるかなぁと思ったので、代表的な探索アルゴリズムを2つ、ソートアルゴリズムを2つ殴り書きます。

ウォーミングアップにどうぞ！

---

###### 1. 線形探索アルゴリズム（データ量小、データ未整列時に適している）
```Python:Python
def linear_search(card_list, card):
    for idx, element in enumerate(card_list):
        if element == card:
            print("{0}番目に{1}はあります".format(idx+1,card))
            return
    print("{0}はありませんでした".format(card))
    return
    
if __name__ == '__main__':
    heart_cards = ["h-5","h-J","h-2","h-9","h-1","h-7",\
                    "h-K","h-4","h-10","h-3","h-6","h-8","h-Q"]
    heart_king = "h-K"
    linear_search(heart_cards,heart_king)
```

ランダムに格納されたリストから、enumerate文を使用し、インデックスと要素にてリストの何番目にあるか表示する超シンプルなアルゴリズムです。

リストの頭から順番に探索をかけます。
効率が悪いとされてますが、使い道がなくはないです。（データ数が少なくて未整列時など） 

余談ですが、enumetateのインデックス部分を「i」とだけ書くことがあまり好きではありません。
__i+1__ より __idx+1__ の方が可読性高くないですか？（ただの自分の好み）

---

###### 2. 二分探索アルゴリズム（データ量大、データ整列済み時に適している）

```Python:Python
def binary_search(card_list, card):
    low = 0
    high = len(card_list) - 1  # 後にindexを用いるため、-1する
    print(high)
    while low <= high:  # lowがhighを超えるまで
        mid = (low + high) // 2  # mid = 4
        if card_list[mid] == card:
            print("{0}番目に{1}はあります".format(mid,card))
            return
        elif card_list[mid] < card:
            low = mid + 1
        else:
            high = mid - 1
    return

if __name__ == '__main__':
    heart_cards = [1,2,4,5,6,8,9,10,12,13]
    heart_eight = 8
    binary_search(heart_cards, heart_eight)
```

二分という名の通り、 __一度中間点（mid）を決定し__ 探索のループをかけます。
よく言われているように、タイトルがあいうえお順になっている紙の辞書で見つけたいページを真ん中から探すイメージですね。

与えられた値と中間点（mid）比較し、相違した場合はmidの値を基準に、lowとhighの値を __「目標に近い方」__ に更新させます。

ループごとに探索範囲がほぼ半減していくので、整列しているデータに対し高速に探索をかけられます。

運よく中間点となる数値が一発目の探索にかけられたら、その時点で処理は終了します。
上記の例ですと、heart_card = 6（インデント番号：5）の場合ですね。

---

###### 3. マージソート（データがバラバラで昇順にしたい時）

```Python:Python
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2  # 商の整数のみ
    left = merge_sort(arr[:mid])  # mid未満
    right = merge_sort(arr[mid:])  # mid以上
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 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
    result.extend(left[i:])
    result.extend(right[j:])
    return result

arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))
```

```:Terminal
[3, 9, 10, 27, 38, 43, 82]
```

データの並びがバラバラなら、基本的に並び替えることで何かと可用性が上がります。
上記アルゴリズムは、バラバラに値が格納されたリストの要素を昇順に並び替えます。

まず、merge_sort関数で与えられたリストの長さを2で整数除算します。結果を、おおよその「中間点（＝mid）」とみなします。
そのmid未満をleftに格納し、mid以上をrightに格納し、merge関数に渡します。

 __この時点では複数の値を真ん中を基準に左右へ振っただけで、まだ整列はしていません。__ 

---

merge関数では、ループ処理のインデックス操作に使用するi, jを0で初期化し
while文にてleftとrightへランダムに振った値を、今度は小さい順に並び変えています。

例として、
```
if left[0] < rihgt[0] # left[0]の中身は43、rihgt[0]の中身は9
```

__False__ なのでelse文の方へ行きますね
```
result.append(right[0]) #（中身は9）
```

j += 1にて、次はrightリストの次の要素 __right[1]__ と __left[0]__ が探索（どっち小さい？）にかけられます。この繰り返しです。

__イメージ__
［leftの箱］［rightの箱］があったとして、

［　　　］ ［　　　］ （初期状態はどっちも空っぽ）
［○　　］ ［　　　］ （探索の結果、leftへアペンド）
［○　　］ ［○　　］ （探索の結果、rightへアペンド）
［○　　］ ［○○　］ （探索の結果、rightへアペンド）

みたいな感じです。

---

繰り返し部分（while）について

```
while i < len(left) and j < len(right):
```
i, jがどちらもがleft, rightの長さと同じになる時、リストの探索が完了した（＝これ以上探索する必要がない状態になった）といえます。

それらは最終的に
```
result.extend(left[i:])
result.extend(right[j:])
```
にて、左から小さい順に整列した二つのリストを
 __result__ という結果格納用のリストに、extendメソッドを用いて再度左から並べています。
結果的に、小さい順（昇順）をresultとして返します。

###### 4. ピポットソート（データがバラバラで昇順にしたい時 その2）
クイックソートともいいます。

```Python:Python
def quick_sort(arr):
    if len(arr) <= 1:
        return arr  # 要素が1つ以下ならそのまま返す（再帰の終了条件）
    
    pivot = arr[len(arr) // 2]  # 配列の中央の要素をピボットに選ぶ
    left = [x for x in arr if x < pivot]  # ピボットより小さい要素
    middle = [x for x in arr if x == pivot]  # ピボットと等しい要素
    right = [x for x in arr if x > pivot]  # ピボットより大きい要素
    
    # 左、真ん中、右を再帰的に結合してソート
    return quick_sort(left) + middle + quick_sort(right)

# 使用例
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print(sorted_arr)
```
```:Terminal
[1, 1, 2, 3, 6, 8, 10]
```

 __基準点（基本真ん中）を一度決定するのは高速なソートアルゴリズムを組む際に大変便利です。__ 
クイックソートも一度基準点を決め、リスト内包表記による分岐で左・真ん中・右のリストに振り分け、それを左から結合して呼び出し先に返しています。

3のマージソートよりコードがスッキリしていますね。

###### （備考）リスト内包表記について
```Python
left = [x for x in arr if x < pivot]
```
上記は __リスト内包表記__ を使って、リストarrの要素をフィルタリングして新しいリスト left を作成しています。
上記の例での目的は、pivotよりも小さい要素だけを抽出し、left というリストに突っ込むことです。

もう少し分解すると...
```Python
x for x in arr  # この部分で、リストarrのすべての要素xに対し、順番に処理を行うことを示します。 
```

```Python
if x < pivot # この部分で、arrの各要素xがpivotより小さいかどうかをチェックします。
```
これらの条件を満たす要素だけが、新しいリスト left に追加されます。

---

なお、昇順・降順の並び替えはPythonのsoretd()メソッドを使うと一瞬で完了します。


```
numbers = [5, 1, 4, 3, 2]

# 昇順（小さい → 大きい）
print(sorted(numbers))  # [1, 2, 3, 4, 5]

# 降順（大きい → 小さい）
print(sorted(numbers, reverse=True))  # [5, 4, 3, 2, 1]
```


おわり