今回はPython言語で
様々なソートプログラムを実装して
色々比較してみました。


解説動画はこちら





今回は
ソートプログラムを比較してみる検証です。

用意したソートプログラムは
こんなのです。

1.バブルソート（Bubble Sort）
2.選択ソート（Selection Sort）
3.挿入ソート（Insertion Sort）
4.マージソート（Merge Sort）
5.クイックソート（Quick Sort）
6.ヒープソート（Heap Sort）
7.シェルソート（Shell Sort）



さてひとつづつ見ていきましょう。

バブルソート（Bubble Sort)


隣接する要素を比較して順番が逆であれば交換を行う
比較的単純なソートアルゴリズムで
効率はあまりよくなく、実装が容易です。
# バブルソート
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]
    return arr



選択ソート（Selection Sort）

配列を走査し、最小値を見つけて
先頭の要素と交換することを繰り返すことで
ソートを行うアルゴリズム

バブルソートよりも効率的です。
# 選択ソート
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]
    return arr


挿入ソート（Insertion Sort）

要素を1つずつ取り出して
適切な位置に挿入していくことで
ソートを行うアルゴリズム

データの量が少ない場合や
すでにほぼソートされている場合には
高速に動作するようです。
# 挿入ソート
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr


マージソート（Merge Sort）

分割統治法を用いた再帰的なアルゴリズムで
データを分割してソートし、それをマージすることで
ソートを行うアルゴリズム

安定かつ効率的なアルゴリズムであり
大きなデータセットに対しても
高速に動作するそうです。
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
    return arr


クイックソート（Quick Sort）

分割統治法を用いた再帰的なアルゴリズムで
ピボットを選択し、それを基準にデータを分割して
ソートするアルゴリズム

一般的に高速でメモリ効率も良いですが
最悪の場合には効率が落ちることがあるそうです。

再帰を用いたものと
再帰無しバージョンがあり
検証は無しバージョンを使用してます。

# クイックソート(再帰あり)
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left = [x for x in arr[1:] if x < pivot]
        right = [x for x in arr[1:] if x >= pivot]
        return quick_sort(left) + [pivot] + quick_sort(right)

再帰無し
# 再帰なし
def quick_sort(arr):
    size = len(arr)
    stack = [(0, size - 1)]
    while stack:
        start, end = stack.pop()
        if start >= end:
            continue

        pivot = arr[end]
        low = start
        high = end - 1

        while low <= high:
            if arr[low] > pivot and arr[high] < pivot:
                arr[low], arr[high] = arr[high], arr[low]
                low += 1
                high -= 1
            if arr[low] <= pivot:
                low += 1
            if arr[high] >= pivot:
                high -= 1

        arr[low], arr[end] = arr[end], arr[low]

        if low - start < end - low:
            stack.append((start, low - 1))
            stack.append((low + 1, end))
        else:
            stack.append((low + 1, end))
            stack.append((start, low - 1))
    return arr




ヒープソート（Heap Sort）

ヒープと呼ばれる特殊なデータ構造を使用して
ソートを行うアルゴリズム

安定でありながらも効率的なソートが可能ですが
実装がやや複雑です。
def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[i] < arr[left]:
        largest = left

    if right < n and arr[largest] < arr[right]:
        largest = right

    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)
    return arr


シェルソート（Shell Sort）

挿入ソートの改良版であり
データを一定の間隔で分割して
ソートを行うアルゴリズム

間隔を縮めながら繰り返し処理を行うことで
最終的にソートされた配列が得られます。
# シェルソート
def shell_sort(arr):
    n = len(arr)
    gap = n // 2

    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr


速度比較

これら7つのソートプログラムを用いて
速度を比較してみましょう。

こちらのコードで比較検証を行いました。
import numpy as np
import time
import sys
sys.setrecursionlimit(20000)

# 関数実行時間チェック
def time_check(name,func,n):
    start_time = time.time()
    val = func(n);
    end_time = time.time()
    print(name, end_time - start_time)

# ソート比較
def compare_sort(n):
    # ソート対象のリスト生成
    arr = [1 for _ in range(n)]
    np.random.shuffle(arr)
    
    # 各ソートアルゴリズムの実行時間計測
    #time_check("バブルソート" , bubble_sort, arr.copy())
    #time_check("選択ソート" , selection_sort, arr.copy())
    time_check("挿入ソート" , insertion_sort, arr.copy())
    #time_check("マージソート" , merge_sort, arr.copy())
    time_check("クイックソート" , quick_sort, arr.copy())
    time_check("ヒープソート" , heap_sort, arr.copy())
    time_check("シェルソート" , shell_sort, arr.copy())

compare_sort(1000)




最後に


とまあ、ソートプログラムを書くのは
プログラミングのお勉強には良いですが
業務上の実益はほぼほぼ無いですねー

そもそもPythonの組み込みソートは
圧倒的に性能が良く

数10万件程度だと
誤差の範囲で終わってしまうので
ソートを業務で実装することは
余り無いですね。

超大規模なデータを用いるような
大掛かりなプロジェクトでなければ
ソートに手を入れて高速化をはかるような
案件に出会えないですかね。

興味がある方は
突き詰めてみるのも面白いかもです。

今回はこれまでです
それでは。

タグ ：
#プログラミング
#Python
#ソート
#並び替え
#sort