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

ソート	Average	Best	Worst	安定	備考
radix	O(n)	O(n)	O(n)	Yes	countソートの改良
quick	O(n log n)	O(n log n)	O(n2)	No	データの比較と交換回数が非常に少ないのが特徴で、ランダムに散らばっているデータに対して、最も効率良く並べ替えを実行
merge	O(n log n)	O(n log n)	O(n log n)	Yes	整列されていないリストを2つのリストに分割して、それぞれを整列させた後、それらをマージして整列済みのひとつのリストを作成
tim	O(n log n)	O(n)	O(n log n)	Yes	insertionソートとmergeソートを使用

• radixソート

from typing import List

def counting_sort(numbers: List[int], place: int) -> List[int]:
    counts = [0] * 10
    result = [0] * len(numbers)

    for num in numbers:
        index = int(num / place) % 10
        counts[index] += 1

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

    i = len(numbers) - 1
    while i >= 0:
        index = int(numbers[i]/place) % 10
        result[counts[index]-1] = numbers[i]
        counts[index] -= 1
        i -= 1

    return result


def radix_sort(numbers: List[int]) -> List[int]:
    max_num = max(numbers)
    place = 1
    while max_num > place:
        numbers = counting_sort(numbers, place)
        place *= 10
    return numbers

• quickソート

from typing import List

def partition(numbers: List[int], low: int, high: int) -> int:
    i = low - 1
    pivot = numbers[high]
    for j in range(low, high):
        if numbers[j] <= pivot:
            i += 1
            numbers[i], numbers[j] = numbers[j], numbers[i]
    numbers[i+1], numbers[high] = numbers[high], numbers[i+1]
    return i+1


def quick_sort(numbers: List[int]) -> List[int]:
    def _quick_sort(numbers: List[int], low: int, high: int) -> None:
        if low < high:
            partition_index = partition(numbers, low, high)
            _quick_sort(numbers, low, partition_index-1)
            _quick_sort(numbers, partition_index+1, high)

    _quick_sort(numbers, 0, len(numbers)-1)
    return numbers

• mergeソート

from typing import List

def merge_sort(numbers: List[int]) -> List[int]:
    if len(numbers) <= 1:
        return numbers

    center = len(numbers) // 2
    left = numbers[:center]
    right = numbers[center:]

    merge_sort(left)
    merge_sort(right)

    i = j = k = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            numbers[k] = left[i]
            i += 1
        else:
            numbers[k] = right[j]
            j += 1
        k += 1

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

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

    return numbers

• timソート

def merge_sort(data: list, l: int, m: int, r: int) -> list:
    len_left, len_right = m - l + 1, r - m
    left, right = [], []
    for i in range(0, len_left):
        left.append(data[l + i])
    for i in range(0, len_right):
        right.append(data[m + 1 + i])

    i, j, k = 0, 0, l
    while i < len_left and j < len_right:
        if left[i] <= right[j]:
            data[k] = left[i]
            i += 1
        else:
            data[k] = right[j]
            j += 1
        k += 1

    while i < len_left:
        data[k] = left[i]
        k += 1
        i += 1

    while j < len_right:
        data[k] = right[j]
        k += 1
        j += 1

    return data


def insertion_sort(data: list, left: int, right: int) -> list:
    for i in range(left + 1, right + 1):
        temp = data[i]
        j = i - 1
        while j >= left and data[j] > temp:
            data[j + 1] = data[j]
            j -= 1

        data[j + 1] = temp
    return data


def tim_sort(data: list, size: int = 32) -> list:
    n = len(data)
    for i in range(0, n, size):
        insertion_sort(data, i, min((i + 31), (n - 1)))

    while size < n:
        for left in range(0, n, 2 * size):
            mid = left + size - 1
            right = min((left + 2 * size - 1), (n - 1))
            merge_sort(data, left, mid, right)
        size = 2 * size
    return data

ソートの紹介は以上になります。
お疲れ様でした。