各種ソートアルゴリズムをPythonで実装

本記事はソートについてPythonを利用しながら、学生エンジニアが初心者の方へ向けて優しく解説しています。ソートとは数値や文字列を昇順や降順に並べ替えることで、プログラミングを学ぶ上で非常に重要な道具です。タブやブックマークなどに保存してご利用ください。

本記事の内容

計算時間と安定性
各種ソートアルゴリズムの特徴
Pythonコード

計算時間と安定性

名称	平均計算時間	最悪計算時間	最良計算時間	安定性
バブルソート	Ｏ（ｎ²）	Ｏ（ｎ²）	Ｏ（ｎ）	◯
シェーカーソート	Ｏ（ｎ²）	Ｏ（ｎ²）	Ｏ（ｎ）	◯
コムソート	Ｏ（n*log(n)）	Ｏ（ｎ²）	Ｏ（n*log(n)）	✕
選択ソート	Ｏ（ｎ²）	Ｏ（ｎ²）	Ｏ（ｎ²）	✕
挿入ソート	Ｏ（ｎ²）	Ｏ（ｎ²）	Ｏ（ｎ）	◯
ノームソート	Ｏ（ｎ²）	Ｏ（ｎ²）	Ｏ（ｎ）	◯
シェルソート	gap（間隔）による	Ｏ（ｎ²）	Ｏ（n*log(n)）	✕
クイックソート	Ｏ（n*log(n)）	Ｏ（ｎ²）	Ｏ（n*log(n)）	✕
マージソート	Ｏ（n*log(n)）	Ｏ（n*log(n)）	Ｏ（n*log(n)）	◯
カウントソート	Ｏ（n）	Ｏ（n）	Ｏ（n）	◯

各種ソートアルゴリズムの特徴

名所	特徴
バブルソート	端から端の値までソートするのに非常に時間がかかる。有名なアルゴリズム。
シェーカーソート	バブルソートの改良版。両端からの２方向でソートを行う。
コムソート	バブルソートの改良版。バブルソートとは違い、初期段階で離れた要素を比較。メモリの使用率が少ない。
選択ソート	データから最小値を探索し、未選択の先頭要素へ値を交換する。安定ソートではなく、改良の余地がある。アルゴリズムが簡単で実装が簡単。バブルソートより若干高速。有名なアルゴリズム。
挿入ソート	既に整列されている部分が多ければ多いほど高速。有名なアルゴリズム。
ノームソート	挿入ソートと非常に類似、バブルソートの改良版ともいえる。非常にシンプルで単純な整列アルゴリズム。
シェルソート	挿入ソートの改良版。初めは間隔のある要素を比較しあい、少しずつ比較する間隔を狭める。「gap」という間隔を利用する。
クイックソート	非常に高速でよく利用される。「pivot」といわれる基準を利用する。有名なアルゴリズム。
マージソート	非常に高速でよく利用される。データを分割してマージ（併合）を行うアルゴリズム。速度が安定していて早いが、並べ替える要素数の数だけメモリが必要。
カウントソート	比較を行う代わりに、数え上げ（カウント）を利用してソートする。無駄なメモリが必要となる場合が多い。

Pythonコード

バブルソート

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

バブルソートは、隣り合う要素を比較しながら整列させます。
並列処理につよく、その改良版はたくさんの場面で使用されています。

バブルソートのアルゴリズムは２重ループで隣接の値同士を比較し合います。
詳しく知りたい方は、下の記事でPythonの実行例とともにバブルソートを解説しています。
>>バブルソートとは

シェーカーソート

def shaker_sort(nums):
    beginning = 0
    ending = len(nums) - 1

    while beginning < ending:
        for i in range(beginning, ending):
            if nums[i] > nums[i+1]:
                nums[i], nums[i+1] = nums[i+1], nums[i]
        ending -= 1

        for i in range(ending - 1, beginning - 1, -1):
            print(i)
            if nums[i] > nums[i+1]:
                nums[i], nums[i+1] = nums[i+1], nums[i]
        beginning += 1

    return nums

シェーカーソートは前から後ろ、後ろから前、と順番にソートしていく整列アルゴリズム。
これにより、１方向のバブソートよりも効率の良いソートが可能。

詳しく知りたい方は、下の記事でPythonの実行例とともにシェーカーソートを解説しています。
>>シェーカーソートとは

コムソート

def comb_sort(nums):
    gap = len(nums)
    swap = True

    while gap != 1 or swap:
        gap = int(gap / 1.3)
        if gap < 1:
            gap = 1
        swap = False

        for i in range(0, len(nums) - gap):
            if nums[i] > nums[i + gap]:
                nums[i], nums[i + gap] = nums[i + gap], nums[i]
                swap = True
    return nums

下にコムソートを６ステップで解説すると、
1. リストの総数を1.3で割り、gapを求める
2. 先頭からの要素とgap分離れた要素の大小関係を比較して入れ替える
3. 2の比較を最後まで繰り返す
4. gapを更に1.3で割り、新しいgapを求める。
5. 2〜3を繰り返す
6. gapが1になれば、入れ替えがなくなるまで比較を行う

ここで、gapが1.3になるのは暗記しておきましょう。

詳しく知りたい方は、下の記事でPythonの実行例とともにコムソートを解説しています。
>>コムソートとは

選択ソート

def selection_sort(nums):
    for i in range(len(nums)):
        min = i
        for j in range(i+1, len(nums)):
            if nums[min] > nums[j]:
                min = j
        nums[i], nums[min] = nums[min], nums[i]
    return nums

下に選択ソートを４ステップで解説しました。
１. 未選択のデータから最小値を探索
２. 最小値を先頭の要素と交換し整列済みのデータと決定する
３. 決定した以降のデータから一番小さい値を探し、未決定の先頭要素と交換
４. １〜３を繰り返す

詳しく知りたい方は、下の記事でPythonの実行例とともに選択ソートを解説しています。
>>選択ソートとは

挿入ソート

def insertion_sort(nums):
    for i in range(1, len(nums)):
        tmp = nums[i]
        j = i - 1

        while j >= 0 and nums[j] > tmp:
            nums[j + 1] = nums[j]
            j -= 1

        nums[j + 1] = tmp

    return nums

下に挿入ソートを３ステップで解説しました。
１．０番目と１番目の要素を比較し、順序が逆であれば入れ換える。
２．2番目の要素について、０番目・１番目の順に比較し、順序が整うように適切な位置へ挿入する
３．3番目以降の要素も同様にして、整列済みデータとの比較と挿入を繰り返す。

詳しく知りたい方は、下の記事でPythonの実行例とともに挿入ソートを解説しています。
>>挿入ソートとは

ノームソート

def gnome_sort(nums):
    value = 0
    while value < len(nums):
        if value == 0:
            value += 1
        if nums >= nums:
            value += 1
        else:
            nums, nums = nums, nums
            value -= 1
    return nums

下にノームソートを３ステップで解説しました。
１．隣接する２つの要素を比較
２．順序が正しければ次の要素を比較、順序が逆であれば入れ替えて前の要素へ移動
３．１〜２を繰り返す

詳しく知りたい方は、下の記事でPythonの実行例とともにノームソートを解説しています。
>>ノームソートとは

シェルソート

def shell_sort(nums):
    gap = len(nums) // 2
    while gap > 0:
        for i in range(gap, len(nums)):
            tmp = nums[i]
            j = i
            while j >= gap and nums[j - gap] > tmp:
                nums[j] = nums[j - gap]
                j -= gap
            nums[j] = tmp
        gap //= 2
    return nums

下にシェルソートを３ステップで解説しました。
１．一定間隔ごとに要素を比較して並べ替え
２．間隔を狭めて、１の操作を繰り返す
３．一定間隔が０になればソート完了

今回は、「gap = n / 2（nは先頭要素）」という考え方を利用。

詳しく知りたい方は、下の記事でPythonの実行例とともにシェルソートを解説しています。
>>シェルソートとは

クイックソート

def partition(nums, beginning, ending):
    i = beginning - 1
    pivot = nums[ending]
    for j in range(beginning, ending):
        if nums[j] <= pivot:
            i += 1
            nums[i], nums[j] = nums[j], nums[i]
    nums[i + 1], nums[ending] = nums[ending], nums[i + 1]
    return i+1

下にクイックソートを４ステップで表しました。
１．「pivot」を決定する
２．左から要素を順番に調べ、「pivot」以上であればそのインデックスをiとする。
３．左から要素を順番に調べ、「pivot」以下であればそのインデックスをjとする。
４−１．iがjより左ならば、要素を入れ替え「２」の処理へ戻る。（「2」はiの一つ右の要素から、「3」はjの一つ左の要素から探索を再開）
４−２．iがjより右ならば、iの左側を境にリストを分割（パーテーション）。分割したそれぞれのグループに対して「1」の処理へ戻る。ここで、1以下の要素数のグループができた場合、そのグループは確定とする。全てのグループが確定した場合、ソート完了。

詳しく知りたい方は、下の記事でPythonの実行例とともにクイックソートを解説しています。
>>クイックソートとは

マージソート

def merge_sort(nums):
    if len(nums) <= 1:
        return nums

    #２分割
    split = len(nums) // 2
    left = nums[:split]
    right = nums[split:]

    #要素数が１になるまで繰り返し分割（再帰関数）
    left = merge_sort(left)
    right = merge_sort(right)

    #マージ（併合）処理
    i, j, k= 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            nums[k] = left[i]
            i += 1
        else:
            nums[k] = right[j]
            j += 1
        k += 1

    while i < len(left):
        nums[k] = left[i]
        i += 1
        k += 1

    while j < len(right):
        nums[k] = right[j]
        j += 1
        k += 1

    return nums

下にマージソートの手順を３ステップでまとめました。
１．データの要素を２分割する
２．分割したデータを整列する
３．整列したデータをマージする

詳しく知りたい方は、下の記事でPythonの実行例とともにマージソートを解説しています。
>>マージソートとは

カウントソート

def count_sort(nums):
    max_num = max(nums)
    elements = [0] * (max_num + 1)
    ans = [0] * len(nums)

    for num in nums:
        elements[num] += 1

    for i in range(1, len(elements)):
        elements[i] += elements[i - 1]

    i = len(nums) - 1
    while i >= 0:
        index = nums[i]
        ans[elements[index] - 1] = nums[i]
        elements[index] -= 1
        i -= 1
    return ans

カウントソートは出現頻度を計算し、出現頻度リストに格納。
リストの要素を出現頻度リストにおけるインデックスとして記憶することで，要素の順番を整列します。

詳しく知りたい方は、下の記事でPythonの実行例とともにカウントソートを解説しています。
>>カウントソートとは