【Udemy】アルゴリズム・データ構造入門 ソート #3.2

ron-tech.hatenablog.com
↑の続きで、引き続き各種ソートの紹介を行います。

ソート	Average	Best	Worst	安定	備考
gnome	O(n2)	O(n)	O(n2)	Yes	bubble sortに類似
insertion	O(n2)	O(n)	O(n2)	Yes	整列済のデータ列に適切に新データを挿入していくようにソートを行う
bucket	O(n+k)	O(n+k)	O(n2)	Yes	あらかじめデータがとりうる値すべての容器(バケット)を順番どおりに並べて用意しておき、値を対応する容器に移すことでソートを行う
shell	Depends on gap sequence	O(n log n)	O(n2)	No	insertion sortの改良 リストにおいてあらかじめ離れている要素を交換しておき、最終的に挿入ソートを実行
counting	O(n)	O(n)	O(n)	Yes	数字が入りうる空の配列を予め用意し、要素をカウントする。

• gnomeソート：後ろの要素と比較して入れ替えていくと、入れ替えた時のみ戻って比較を行うことで並び替える。

from typing import List

def gnome_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    index = 0
    while index < len_numbers:
        if index == 0:
            index += 1
        if numbers[index] >= numbers[index-1]:
            index += 1
        else:
            numbers[index], numbers[index-1] = numbers[index-1], numbers[index]
            index -= 1

    return numbers

• insertionソート：隣り合った要素を比べて順番にソートする方法で、整列済みの部分に対して後ろにある要素をどこに入れるのかを探る。

from typing import List

def insertion_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    for i in range(1, len_numbers):
        temp = numbers[i]
        j = i - 1

        while j >= 0 and numbers[j] > temp:
            numbers[j + 1] = numbers[j]
            j -= 1

        numbers[j + 1] = temp

    return numbers

• bucketソート：予めデータがとりうる値すべての容器を順番どおりに並べて用意しておき、値を対応する容器に移す。

from typing import List

def insertion_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    for i in range(1, len_numbers):
        temp = numbers[i]
        j = i - 1

        while j >= 0 and numbers[j] > temp:
            numbers[j + 1] = numbers[j]
            j -= 1

        numbers[j + 1] = temp

    return numbers

def bucket_sort(numbers: List[int]) -> List[int]:
    max_num = max(numbers)
    len_numbers = len(numbers)
    size = max_num // len_numbers

    buckets = [[] for _ in range(size)]
    for num in numbers:
        i = num // size
        if i != size:
            buckets[i].append(num)
        else:
            buckets[size-1].append(num)

    for i in range(size):
        insertion_sort(buckets[i])

    result = []
    for i in range(size):
        result += buckets[i]

    return result

• shellソート：リストにおいてあらかじめ離れている要素を交換しておき、最終的に挿入ソートを実行。

from typing import List

def shell_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    gap = len_numbers // 2
    while gap > 0:
        for i in range(gap, len_numbers):
            temp = numbers[i]
            j = i
            while j >= gap and numbers[j-gap] > temp:
                numbers[j] = numbers[j-gap]
                j -= gap
            numbers[j] = temp
        gap //= 2

    return numbers

• countingソート：数字が入りうる空の配列を予め用意し、要素をカウントする。

from typing import List

def counting_sort(numbers: List[int]) -> List[int]:
    max_num = max(numbers)
    counts = [0] * (max_num + 1)
    result = [0] * len(numbers)

    for num in numbers:
        counts[num] += 1

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

    i = len(numbers) - 1
    while i >= 0:
        index = numbers[i]
        result[counts[index]-1] = numbers[i]
        counts[index] -= 1
        i -= 1

    return result

次回でソート紹介は最後になります。
お疲れ様でした。