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

基礎的な内容ですが、普段何気なくライブラリとして使っている各種ソートについてまとめます。

ソート	Average	Best	Worst	安定	備考
bogo	O((n+1)!)	O(n)	∞	No	ただランダムに入れ替えるだけ
bubble	O(n2)	O(n)	O(n2)	Yes	隣接する要素を並び替える。1週毎に右側から大きい順に並んでいく。
cooktail	O(n2)	O(n)	O(n2)	Yes	bubbleソートを双方向にすることで若干の効率化を図る。
comb	O(n2**g)	O(n log n)	O(n2)	Yes	bubbleでは隣接する要素を比較・交換するが、combソートでは適当な間隔(慣習的に1.3)のデータに対して比較・交換を行う。g=n//1.3
selection	O(n2)	O(n2)	O(n2)	Yes	最大値を探索して配列最後の要素と入れ替える。

• bogoソート：ただランダムに値を入れ替える。

from typing import List

def in_order(numbers: List[int]) -> bool:
    return all(numbers[i] <= numbers[i+1] for i in range(len(numbers)-1))

def bogo_sort(numbers: List[int]) -> List[int]:
    while not in_order(numbers):
        random.shuffle(numbers)
    return numbers

• bubbleソート：隣接する要素を比較して並び替える。1週毎に右側から大きい順に要素がならんでいく。

from typing import List

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

• cooktailソート：bubbleソートを双方向にすることで若干の効率化を図る。

from typing import List

def cocktail_sort(numbers:List[int]) -> List[int]:
    len_numbers = len(numbers)
    swapped = True
    start = 0
    end = len_numbers - 1
    while swapped:
        swapped = False

        for i in range(start, end):
            if numbers[i] > numbers[i+1]:
                numbers[i], numbers[i+1] = numbers[i+1], numbers[i]
                swapped = True

        if not swapped: break

        swapped = False
        end = end - 1

        for i in range(end-1, start-1,-1):
            if numbers[i] > numbers[i+1]:
                numbers[i], numbers[i+1] = numbers[i+1], numbers[i]
                swapped = True

        start = start + 1

    return numbers

• combソート：bubbleでは隣接する要素を比較・交換するが、combソートでは適当な間隔(慣習的に1.3)のデータに対して比較・交換を行う。

from typing import List

def comb_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    gap = len_numbers
    swapped = True

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

        swapped = False

        for i in range(0, len_numbers - gap):
            if numbers[i] > numbers[i + gap]:
                numbers[i], numbers[i + gap] = numbers[i + gap], numbers[i]
                swapped = True
    return numbers

• selectionソート：最大値を探索して配列最後の要素と入れ替える。

from typing import List

def selection_sort(numbers: List[int]) -> List[int]:
    for i in range(len(numbers)):
        min_idx = i
        for j in range(i+1, len(numbers)):
            if numbers[min_idx] > numbers[j]:
                min_idx = j

        numbers[i], numbers[min_idx] = numbers[min_idx], numbers[i]
    return numbers

コードを実装してみると、理解が深まりますね。
お疲れ様でした。