以下は、クイックソートの実装コードです。

# 左側の要素がすでに処理された場合、右側から探してtempより小さい値をleftに配置します。
while right > left:  # rightとleftの間に要素がある限りループを続けます
    while lis[right] >= temp and right > left:  # rightの値がtemp以上なら、その値はそのままにしてrightを左へ移動
        right -= 1
    lis[left] = lis[right]  # rightの値がtempより小さければ、それをleftに移動し、ループ終了
    while lis[left] <= temp and right > left:  # leftの値がtemp以下なら、その値はそのままにしてleftを右へ移動
        left += 1
    lis[right] = lis[left]  # leftの値がtempより大きければ、それをrightに移動し、ループ終了
lis[left] = temp  # rightとleftが一致したので、tempの値を現在の位置に配置
return left  # tempのインデックスを返す。つまり分割点を示す

def quick_sort(lis, left, right):  
    if right > left:  
        mid = partition(lis, left, right)  # 分割点を取得し、再帰的に範囲を調整
        quick_sort(lis, left, mid - 1)  # 左側を再帰的にソート
        quick_sort(lis, mid + 1, right)  # 右側を再帰的にソート
    return lis

item = [5, 1, 4, 3, 6, 2]  
print(item)  
print(quick_sort(item, 0, len(item) - 1))  # 全体を対象に初期化

出力結果：

クイックソートの時間計算量はO(nlogn)です。

しかし、最悪のケースが存在します。例えば、昇順で並べ替えたいリストが[9,8,7,6,5,4,3,2,1]の場合、再帰的に処理される状況は以下のようになります。

• [9,8,7,6,5,4,3,2,1] -- 9が正しい位置に移動
• [1,8,7,6,5,4,3,2,9] -- 1が正しい位置に移動
• [1,8,7,6,5,4,3,2,9] -- 8が正しい位置に移動
• [1,2,7,6,5,4,3,8,9] -- 2が正しい位置に移動
• [1,2,7,6,5,4,3,8,9] -- 7が正しい位置に移動
• [1,2,3,6,5,4,7,8,9] -- 3が正しい位置に移動
• [1,2,3,6,5,4,7,8,9] -- 6が正しい位置に移動
• [1,2,3,4,5,6,7,8,9] -- 4が正しい位置に移動
• [1,2,3,4,5,6,7,8,9] -- ソート完了

黄色の領域は各再帰の処理対象を示しています。このように、各ステップで1つの要素が正しく配置され、残りの要素数は1つ減っていきます。このようなケースでは、計算量はO(n²)となります。ただし、発生確率は低いです。

解決策として、最初の要素を基準にする前にランダムな要素を交換することで対応できます。

二、ヒープソート

2.1 木構造について

木とは、データ構造の一種です。

木は再帰的に定義されるデータ構造であり、n個のノードからなる集合です。

• n=0のとき、空の木
• n>0のとき、根ノードを持つ木があり、他のノードはm個の集合に分かれており、それぞれがまた木構造である

2.1.1 二分木

次数が2以下の木。つまり、各ノードは最大2つの子ノードを持ち、左と右に分ける。

満足二分木と完全二分木

ヒープは特殊な完全二分木です。

二分木の表現方法には、連結リストによる表現と配列による表現があります。

2.2 ヒープソート

ヒープは特別な完全二分木です。

• 最大ヒープ：任意のノードがその子ノードより大きい
• 最小ヒープ：任意のノードがその子ノードより小さい

2.2.1 ヒープの下向き調整

根ノードの左右の部分木がヒープであるが、根ノードがヒープ条件を満たさない場合、一度の下向き調整でヒープに変換できます。

# ヒープの下向き調整
def sift(lis, low, high):  
    """:param lis:リスト
       :param low:根ノードの位置
       :param high:ヒープの最後の要素の位置
    """
    i = low  # iは最初根ノードを指す
    j = 2 * i + 1  # jは最初左子ノードを指す
    temp = lis[i]  # 根ノードを一時保存

    while j <= high:  # jが範囲内であればループ
        if j + 1 <= high and lis[j + 1] > lis[j]:  # 右子ノードが存在し、より大きい場合
            j = j + 1  # jを右子ノードに更新
        if lis[j] > temp:
            lis[i] = lis[j]  # 子ノードが根ノードより大きい場合、入れ替える
            i = j
            j = 2 * i + 1
        else:
            lis[i] = temp  # 根ノードが大きい場合、元に戻す
            break
    else:  # jが範囲外になった場合、tempをiの位置に置く
        lis[i] = temp

item = [3,9,8,5,4,7,6,1,2]  
print(item)  
sift(item, 0, len(item) - 1)  
print(item)

2.2.2 ヒープソートのプロセス

1. ヒープ（最大ヒープ）を作成し、根ノードが最大値になる
2. ヒープの根ノードを最大値として取り出し、末尾に移動
3. 末尾の要素を根ノードと交換し、再度ヒープを調整
4. 最大値を順番に末尾に移動させることでソート完了

def heap_sort(lis):  
    # ヒープの構築
    n = len(lis)  
    for i in range((n - 2) // 2, -1, -1):  
        sift(lis, i, n - 1)  # ヒープの各部分木に対して下向き調整

    # ヒープソートの実行
    for i in range(n - 1, -1, -1):  
        lis[0], lis[i] = lis[i], lis[0]  # 根ノードと末尾を交換
        sift(lis, 0, i - 1)  # ヒープ再構築

item = [3,5,8,4,9,7,2,1,6]  
print(item)  
heap_sort(item)  
print(item)

時間計算量：O(nlogn)

2.2.3 ヒープソートの組み込みモジュール - heapq

heapq.heapify(lis) -- 最小ヒープを構築

heapq.heappop(heap) -- ヒープ内の最小要素を取り出し、ヒープを維持

import heapq

item = [3, 5, 8, 4, 9, 7, 2, 1, 6]  
print(item)  
heapq.heapify(item)  # 最小ヒープを構築
print(item)  
for i in range(len(item)):  
    a = heapq.heappop(item)  # 最小要素を順次取り出す
    print(a, end=",")  
print(item)

2.2.4 ヒープソートの応用 - TopK問題

n個の数からk個の最大値を求めるアルゴリズムを設計してください（k<n）。

• ソートしてスライス：時間計算量 O(nlogn)
• バブルソート/選択ソート/挿入ソート：時間計算量 O(kn)
• ヒープソート：時間計算量 O(nlogk)

ヒープソートの手順：

1. リストの前k個の要素で最小ヒープを構築
2. 残りの要素を走査し、ヒープの根ノードより大きい場合は置き換え、再調整
3. ヒープの根ノードを順次取り出し、ソート

# 下向き調整 - 最小ヒープ
def sift(lis, low, high):  
    i = low  
    j = 2 * i + 1  
    tmp = lis[i]

    while j <= high:
        if j + 1 <= high and lis[j + 1] < lis[j]:
            j = j + 1
        if lis[j] < tmp:
            lis[i] = lis[j]
            i = j
            j = 2 * i + 1
        else:
            lis[i] = tmp
            break
    else:
        lis[i] = tmp

# TopKの実装
def topk(lis, k):  
    heap = lis[0:k]  # 前k個の要素を抽出
    # 1. 最小ヒープを構築
    for i in range((k - 2) // 2, -1, -1):  
        sift(heap, i, k - 1)  
    # 2. 残りの要素を処理
    for i in range(k, len(lis)):  
        if lis[i] > heap[0]:  
            heap[0] = lis[i]  
            sift(heap, 0, k - 1)  
    # 3. ヒープの要素を逆順に取り出し
    for i in range(k - 1, -1, -1):  
        heap[0], heap[i] = heap[i], heap[0]  
        sift(heap, 0, i - 1)  
    return heap

import random
item = [i for i in range(100)]  
random.shuffle(item)  
print(item)  
heap = topk(item, 10)  
print(heap)

三、マージソート

3.1 マージの概念

リストが2つのソート済み部分に分けられている場合、それらを1つのソート済みリストに結合する方法を説明します。