並べ替え（アルゴリズム）

　　Pythonで６種類の並べ替えアルゴリズムを調べる
　　　　昇順に並べ替えることを前提とする（降順は内容を読み替えてください）

１．バブルソート

　隣同士の値を比較、必要があれば入れ替え、を繰り返して整列させる
　　　計算回数は、O(n^2)

　サンプルコード

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# 使用例
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("ソート済み配列：")
for i in range(len(arr)):
    print("%d" %arr[i]),

２．クイックソート

　基準値を設けて、基準値より大きいブロックと小さいブロックに分けて並び替える
　　　計算回数は、O(n log n)

　サンプルコード

def quick_sort(arr, low, high):
    if low < high:
        # pivotを決定する
        pivot_index = partition(arr, low, high)

        # pivotを中心に左側をソートする
        quick_sort(arr, low, pivot_index - 1)
        # pivotを中心に右側をソートする
        quick_sort(arr, pivot_index + 1, high)

def partition(arr, low, high):
    # pivotを最後の要素に設定する
    pivot = arr[high]
    # pivotより小さい要素を左側に、大きい要素を右側に配置する
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    # pivotを適切な位置に配置する
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1

# 使用例
arr = [64, 34, 25, 12, 22, 11, 90]
n = len(arr)
quick_sort(arr, 0, n-1)
print("ソート済み配列：")
for i in range(n):
    print("%d" % arr[i]),

３．マージソート

　対象のデータを分割し、分割後の小さいブロック内で整列、再度統合する
　　　計算回数は、O(n log n)

　サンプルコード

def merge_sort(arr):
    if len(arr) > 1:
        # 中央の位置を求める
        mid = len(arr) // 2

        # 左側と右側に分割する
        left_half = arr[:mid]
        right_half = arr[mid:]

        # 左側と右側を再帰的にソートする
        merge_sort(left_half)
        merge_sort(right_half)

        # ソート済みの左側と右側をマージする
        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # 左側に残った要素を配列にコピーする
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        # 右側に残った要素を配列にコピーする
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# 使用例
arr = [64, 34, 25, 12, 22, 11, 90]
merge_sort(arr)
print("ソート済み配列：")
for i in range(len(arr)):
    print("%d" %arr[i]),

４．選択ソート

　データ内の最小値（最大値）の値を見つけて、左から順番に並び替える
　　　計算回数は、o(n^2)

　サンプルコード

def selection_sort(arr):
    n = len(arr)
    # 配列の先頭から末尾まで、最小値を選択して配置する
    for i in range(n):
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]

# 使用例
arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print("ソート済み配列：")
for i in range(len(arr)):
    print("%d" %arr[i]),

５．挿入ソート

　左から順番に要素を比較しながら入れ替えていく方法
　　　計算回数は、最大でn(n-1)/2

　サンプルコード

def insertion_sort(arr):
    n = len(arr)
    # 配列の先頭から末尾まで、要素を挿入して配置する
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

# 使用例
arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(arr)
print("ソート済み配列：")
for i in range(len(arr)):
    print("%d" %arr[i]),

６．ヒープソート

　二分木（親１に対して子２のツリー構造）の一種を構築して並べ替えをおこなう
　　　計算回数は、O(n log n)

　サンプルコード

def heapify(arr, n, i):
    largest = i  # 親ノード
    l = 2*i + 1  # 左の子ノード
    r = 2*i + 2  # 右の子ノード

    # 左の子ノードが親ノードより大きい場合
    if l < n and arr[largest] < arr[l]:
        largest = l

    # 右の子ノードが親ノードより大きい場合
    if r < n and arr[largest] < arr[r]:
        largest = r

    # 親ノードが最大値でない場合、親ノードと最大値を交換する
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]

        # 子ノードのヒープも修正する
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # 最初に、配列をヒープ構造にする
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # ヒープから一つずつ最大値を取り出して、配列の末尾に配置する
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 最大値を末尾に配置
        heapify(arr, i, 0)  # 未ソート部分のヒープを再構築する

# 使用例
arr = [64, 34, 25, 12, 22, 11, 90]
heap_sort(arr)
print("ソート済み配列：")
for i in range(len(arr)):
    print("%d" %arr[i]),