Algorithm #1 Sorting

このノートでは主に sorting algorithm について扱います。この一連のノートでは pseudocode を使用します。algorithm の実装において data structure が極めて重要である場合を除き、実装そのものよりも algorithm 自体に焦点を当てます。

以下の表は、一般的な sorting algorithm の Cheat Sheet です。

$O(n^2)$ Complexity の Sorting

sorting を理解するには、直感的な言葉と code の両方で説明できる必要があります。

sorting の問題は次のように要約できます：

• Input: $N$ 個の順序付けられていない要素（< による全順序を持つ）。
• Output: 昇順に並べられた $N$ 個の要素。

まずは $O(n^2)$ の sorting から始めましょう。

Selection Sort

言葉での説明：

• Step 0: index $[0, n-1]$ の範囲で最小値を見つけ、それを position 0 の要素と swap する。
• Step 1: index $[1, n-1]$ の範囲で最小値を見つけ、それを position 1 の要素と swap する。
• ...
• Step n-1: index $n-1$ で最小値を見つける（残り1つのため、swap は不要）。

合計 $n$ 回の swap が行われ、各 swap では array の要素を最大 $n$ 個確認する必要があります。したがって、complexity は $O(n^2)$ となります。

pseudocode での説明：

C++for(int i = 0; i < n; i++):
    // 维护每个循环中的最小的数值
    min_index = i
    for(int j = i + 1; j < n; j++):
    // 将 a[i] 与 a[i, length(A)]中最小的元素交换
        if A[j] < A[min_index]
            min_index = j
    swap A[i] and A[min_index]

この algorithm は、$i$ 番目に小さい要素を a[i] に配置します。array の $i$ 番目の位置より左側には最小の $i$ 個の要素が並び、これらに再び access することはありません。

Time Complexity: Worst case $O(n^2)$。

Bubble Sort

• position 0 から始めて、隣接する2つの数値を比較します。前の数値が後ろの数値より大きい場合は、それらの position を