【超基本】初心者に贈るアルゴリズム論 ～ソート・後編～

はじめに

こんにちは。talosです。

前回に引き続きソートのアルゴリズムを説明します。

後編では、「ヒープソート」、「クイックソート」、「マージソート」を説明します。

前編はこちら
talosta.hatenablog.com

ヒープソート

ヒープというデータ構造を用いてソートする方法です。

ヒープとは、常に親ノードの要素より子ノードの要素のほうが小さいか等しい状態を保つ木構造のことです。

つまり、根ノードには常に最大値が格納されるので、根ノードの取り出しを繰り返せばソートできます。

ヒープの整形

ヒープから取り出し

ヒープソートの平均的なオーダーはO(n log n)です。

実装例を下に示します。

def heap_sort(array):
    print('\nstore')
    for k in reversed(range(0, int(len(array) / 2))):
        i = k            # 親ノード
        j = 2 * i + 1    # 子ノード
        x = array[i]
        
        # ヒープの整形
        while j <= len(array) - 1:
            # 二つの子ノードの要素のうち大きい方
            if j < len(array) - 1 and array[j + 1] > array[j]:
                j += 1
            #  親ノードの要素が子ノードの要素より小さければ交換
            if x < array[j]:
                array[i] = array[j]
                i = j
                j = 2 * i + 1
            else:
                break
        
        array[i] = x
        print(array)
    
    print('\ntake out')
    for k in reversed(range(0, len(array) - 1)):
        x = array[k + 1]         # 末尾の要素取り出し（一時的に根ノードに格納）
        array[k + 1] = array[0]  #  最大値を取り出し末尾に（ソート）
        i = 0  # 親ノード　
        j = 1  # 子ノード
        
        # ヒープの整形
        while j <= k:
            if j < k and array[j + 1] > array[j]:
                j += 1
            if x < array[j]:
                array[i] = array[j]
                i = j
                j = 2 * i + 1
            else:
                break
        
        array[i] = x
        print(array)

# ソート対象のリスト
array = [10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3]
print(array)

heap_sort(array)
print('\n--result--')
print(array)

出力

[10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3]

store
[10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3]
[10, 43, 54, 92, 69, 94, 9, 23, 29, 6, 88, 19, 11, 3]
[10, 43, 54, 92, 88, 94, 9, 23, 29, 6, 69, 19, 11, 3]
[10, 43, 54, 92, 88, 94, 9, 23, 29, 6, 69, 19, 11, 3]
[10, 43, 94, 92, 88, 54, 9, 23, 29, 6, 69, 19, 11, 3]
[10, 92, 94, 43, 88, 54, 9, 23, 29, 6, 69, 19, 11, 3]
[94, 92, 54, 43, 88, 19, 9, 23, 29, 6, 69, 10, 11, 3]

take out
[92, 88, 54, 43, 69, 19, 9, 23, 29, 6, 3, 10, 11, 94]
[88, 69, 54, 43, 11, 19, 9, 23, 29, 6, 3, 10, 92, 94]
[69, 43, 54, 29, 11, 19, 9, 23, 10, 6, 3, 88, 92, 94]
[54, 43, 19, 29, 11, 3, 9, 23, 10, 6, 69, 88, 92, 94]
[43, 29, 19, 23, 11, 3, 9, 6, 10, 54, 69, 88, 92, 94]
[29, 23, 19, 10, 11, 3, 9, 6, 43, 54, 69, 88, 92, 94]
[23, 11, 19, 10, 6, 3, 9, 29, 43, 54, 69, 88, 92, 94]
[19, 11, 9, 10, 6, 3, 23, 29, 43, 54, 69, 88, 92, 94]
[11, 10, 9, 3, 6, 19, 23, 29, 43, 54, 69, 88, 92, 94]
[10, 6, 9, 3, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94]
[9, 6, 3, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94]
[6, 3, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94]
[3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94]

--result--
[3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94]

クイックソート

クイックソートは名前の通り速く、よく使われます。

配列の中のある要素xより大きいグループと小さいグループに分け、それぞれのグループを再帰的にソートします。

※ オレンジの箇所は基準値

クイックソートのオーダーはO(n log n)です

実装例を下に示します。

def quick_sort(array, low, high):
    if low < high:
        mid = int((low + high) / 2)  # 基準値
        x = array[mid]
        i = low
        j = high
        print('low=' + str(array[low]) + ' mid=' + str(array[mid]) + ' high=' + str(array[high]))
        
        # 左側にxより大きい要素があり、右側にxより小さい要素があれば交換
        # どちらかが欠けている場合はxをずらす
        while i <= j:
            while array[i] < x:
                i += 1
            while array[j] > x:
                j -= 1
            if i <= j:
                array[i], array[j] = array[j], array[i]
                i += 1
                j -= 1
        
        print(array)

        quick_sort(array, low, j)
        quick_sort(array, i, high)

# ソート対象のリスト
array = [10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3]
print(array)

quick_sort(array, 0, len(array) - 1)
print('\n--result--')
print(array)

出力

[10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3]
low=10 mid=9 high=3
[3, 6, 9, 92, 69, 11, 54, 23, 29, 43, 88, 19, 94, 10]
low=3 mid=6 high=9
[3, 6, 9, 92, 69, 11, 54, 23, 29, 43, 88, 19, 94, 10]
low=92 mid=29 high=10
[3, 6, 9, 10, 19, 11, 29, 23, 54, 43, 88, 69, 94, 92]
low=10 mid=11 high=23
[3, 6, 9, 10, 11, 19, 29, 23, 54, 43, 88, 69, 94, 92]
low=10 mid=10 high=11
[3, 6, 9, 10, 11, 19, 29, 23, 54, 43, 88, 69, 94, 92]
low=19 mid=29 high=23
[3, 6, 9, 10, 11, 19, 23, 29, 54, 43, 88, 69, 94, 92]
low=19 mid=19 high=23
[3, 6, 9, 10, 11, 19, 23, 29, 54, 43, 88, 69, 94, 92]
low=54 mid=88 high=92
[3, 6, 9, 10, 11, 19, 23, 29, 54, 43, 69, 88, 94, 92]
low=54 mid=43 high=69
[3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 94, 92]
low=54 mid=54 high=69
[3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 94, 92]
low=88 mid=94 high=92
[3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94]
low=88 mid=88 high=92
[3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94]

--result--
[3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94]

マージソート

マージソートには二つの方法があります。

1つは、長さ1の列から始め、毎回2つの連続する列をマージする操作を繰り返す方法です。

もう1つは、分割統治法に基づいたものです。

毎回、列を中央で2つのグループに分け、それぞれを再帰的にソートした後、マージします。

ただし、列の長さが十分に短くなったときは、インサーションソートなどの方法でソートします。

ここでは後者の実装例を下に示します。

def merge_sort(array):
    if len(array) <= 3:
        insertion_sort(array)
        return array
    
    mid = int(len(array) / 2)
    # 分割
    arrayA = array[:mid]
    arrayB = array[mid:]
    print('devide')
    print(arrayA, arrayB)
    
    arrayA = merge_sort(arrayA)
    arrayB = merge_sort(arrayB)
    
    return merge(arrayA, arrayB)

def merge(arrayA, arrayB):
    print('merge')
    result_array = []
    
    while len(arrayA) != 0 and len(arrayB) != 0:
        if arrayA[0] < arrayB[0]:
            result_array.append(arrayA.pop(0))
        else:
            result_array.append(arrayB.pop(0))
    
    while len(arrayA) != 0:
        result_array.append(arrayA.pop(0))
    while len(arrayB) != 0:
        result_array.append(arrayB.pop(0))
            
    print(result_array)
    return result_array

def insertion_sort(array):
    print('insertion sort')
    for i in range(1, len(array)):
        x = array[i]
        j = i
        
        # ソート済みの列を右から走査
        while j > 0 and array[j - 1] > x:
            array[j] = array[j - 1]
            j -= 1
        
        array[j] = x
        print(array)

# ソート対象のリスト
array = [10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3]
print(array)

sorted_array = merge_sort(array)
print('\n--result--')
print(sorted_array)

出力

# ソート対象のリスト
array = [10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3]
print(array)

sorted_array = merge_sort(array)
print('\n--result--')
print(sorted_array)
# ソート対象のリスト
array = [10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3]
print(array)
​
sorted_array = merge_sort(array)
print('\n--result--')
print(sorted_array)
[10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3]
devide
[10, 43, 54, 92, 69, 11, 9] [23, 29, 6, 88, 19, 94, 3]
devide
[10, 43, 54] [92, 69, 11, 9]
insertion sort
[10, 43, 54]
[10, 43, 54]
devide
[92, 69] [11, 9]
insertion sort
[69, 92]
insertion sort
[9, 11]
merge
[9, 11, 69, 92]
merge
[9, 10, 11, 43, 54, 69, 92]
devide
[23, 29, 6] [88, 19, 94, 3]
insertion sort
[23, 29, 6]
[6, 23, 29]
devide
[88, 19] [94, 3]
insertion sort
[19, 88]
insertion sort
[3, 94]
merge
[3, 19, 88, 94]
merge
[3, 6, 19, 23, 29, 88, 94]
merge
[3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94]

--result--
[3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94]

おわりに

今回は「ヒープソート」、「クイックソート」、「マージソート」について説明しました。

ソートを1から実装することはあまりないと思いますが、どこかで役に立つかもしれませんので覚えておきましょう。

あわせて読みたい

talosta.hatenablog.com

参考

アルゴリズム論 /オ-ム社/浅野哲夫

posted with カエレバ

楽天市場

Amazon

Yahooショッピング