algorithm/sorting

ソート

2024-04-26

アルゴリズム学習メモ

↓ 比較ソートのシミュレーションを行うツール

Sorting Simulation | Tools

Visualization of sorting algorithms

tools.t3x.jp

挿入ソート

最悪計算量 $O(n^2)$
平均計算量 $O(n^2)$

1 から最後まで順に、その要素の左の要素に対し比較し、適切な位置に置く。

1
def insertion_sort(A, N):
2
    for i in range(1, N):
3
        v = A[i]
4
        j = i - 1
5
        while j >= 0 and A[j] > v:
6
            A[j + 1] = A[j]
7
            j -= 1
8
        A[j + 1] = v

バブルソート

最悪計算量 $O(n^2)$
平均計算量 $O(n^2)$

末尾の要素から最小値比較を行う。これをソートが完了するまで行う。

1
def bubble_sort(A, N):
2
    flag = 1
3
    i = 0
4
    while flag:
5
        flag = 0
6
        for j in range(N-1, i, -1):
7
            if A[j] < A[j - 1]:
8
                A[j], A[j - 1] = A[j - 1], A[j]
9
                flag = 1
10
        i += 1

選択ソート

最悪計算量 $O(n^2)$
平均計算量 $O(n^2)$

未ソート部の最小値と未ソート部の先頭を入れ替える。これをN-1回行う。

1
def selection_sort(A, N):
2
    for i in range(0, N):
3
        min_j = i
4
        for j in range(i, N):
5
            if A[j] < A[min_j]:
6
                min_j = j
7
        A[i], A[min_j] = A[min_j], A[i]

マージソート

最悪計算量 $O(n\log{n})$
平均計算量 $O(n\log{n})$

再帰的に 2 つの部分配列に分割し、ソート済み配列を merge して統合する。

1
def merge(A, l, m, r):
2
    nL = m - l + 1
3
    nR = r - m
4
    L = A[l:m + 1]
5
    R = A[m + 1:r + 1]
6
    i, j, k = 0, 0, l
7
    while i < nL and j < nR:
8
        if L[i] <= R[j]:
9
            A[k] = L[i]
10
            i += 1
11
        else:
12
            A[k] = R[j]
13
            j += 1
14
        k += 1
15
    while i < nL:
16
        A[k] = L[i]
17
        i += 1
18
        k += 1
19
    while i < nR:
20
        A[k] = R[j]
21
        j += 1
22
        k += 1
23

24
def merge_sort(A, l, r):
25
    if l < r:
26
        m = (l + r) // 2
27
        merge_sort(A, l, m)
28
        merge_sort(A, m + 1, r)
29
        merge(A, l, m, r)

クイックソート

最悪計算量 $O(n^2)$
平均計算量 $O(n\log{n})$

再帰的に、partition を用いて最後の要素を基準にし配列を 2 分し、quickSort を行う。

1
def partition(A, p, r):
2
    x = A[r]
3
    i = p - 1
4
    for j in range(p, r):
5
        if A[j] <= x:
6
            i += 1
7
            A[i], A[j] = A[j], A[i]
8
    A[i + 1], A[r] = A[r], A[i + 1]
9
    return i + 1
10

11
def quick_sort(A, p, r):
12
    if p < r:
13
        q = partition(A, p, r)
14
        quick_sort(A, p, q - 1)
15
        quick_sort(A, q + 1, r)

計数ソート

最悪計算量 $O(n+k)$

各要素の出現個数をカウントし、それに基づいてそれを用いて順々にソートする。

1
def counting_sort(A, B, k):
2
    C = [0] * (k + 1)
3
    for j in range(len(A)):
4
        C[A[j]] += 1
5
    for i in range(1, k + 1):
6
        C[i] += C[i - 1]
7
    for j in range(len(A) - 1, -1, -1):
8
        B[C[A[j]] - 1] = A[j]
9
        C[A[j]] -= 1

コムソート

最悪計算量 $O(n^2)$
平均計算量 $O(n\log{n})$

バブルソートの改良版。適当な間隔で整列後、間隔を少しずつ狭めて整列していく。

基数ソート

最悪計算量 $O(nk)$
平均計算量 $O(nk)$

下の桁から順番にソートし、最後に最上位桁でソートする。

シェルソート

最悪計算量 $O(n^{1.5})$
平均計算量 $O(n\log{n})$

挿入ソートの改良版。配列の中である程度間隔が離れた要素の組ごとに挿入ソートを行い、間隔を小さくしながら同様のソートを繰り返す。