개요

기본적인 정렬 알고리즘의 개요와 Python에 의한 구현 예를 정리했습니다.　

삽입 정렬(Insertion Sort)

개요

삽입 정렬은 손에 든 트럼프를 정렬하는 방법에 비유되는 방법입니다. 배열을 소트 끝난 부분과 미소트의 부분으로 나누어 생각해, 미소트 부분의 요소를 소트 부분의 확실한 위치에 삽입해 가는 이미지입니다. 평균 계산 시간·최악 계산 시간은 모두 O($n^2$)입니다만, 어느 정도 정렬된 데이터에 대해서는 고속으로 동작합니다. 안정적인 정렬 알고리즘입니다.

구현 예

# 配列aを挿入ソートで昇順に並べ替える
def insertion_sort(a):
    for i in range(len(a) - 1):
        # a[i]の一つ右の要素: a[j]をソート対象に定める
        j = i + 1

        # a[j]がソート済みの位置に収まるまで繰り返す
        while i >= 0:
            # a[j]を一つ左の要素と比較し、a[j]の方が小さければ交換する
            if a[j] < a[i]:
                a[i], a[j] = a[j], a[i]
                # 比較対象が左に移動しているので、indexを1ずつ減らす
                i -= 1
                j -= 1
            else:
                break

참고

h tp : // Judge. 우아이즈. 아 c. jp / 온 네쥬 드게 /에서 sc 리 p 치온. jsp? 아니 d = A LDS1_1_A
https://ko.wikipedia.org/wiki/삽입 정렬

버블 정렬 (Bubble Sort)

개요

버블 소트는 인접하는 요소로 크고 작은 것이 반대로 되어 있는 것을 교환해 가는 수법입니다. 아래 그림과 같이 열의 말미로부터 요소의 교환을 실시해 가는 경우, 열의 선두로부터 순서에 소트되어 가는 이미지입니다. 버블 정렬로 정렬하는 데 필요한 요소의 교환 횟수는 반전 수 (전도 수)라고하며 열의 혼란 상태를 나타내는 수치로 사용됩니다. 평균 계산 시간, 최악 계산 시간은 모두 O($n^2$)로, 안정(stable)인 정렬 알고리즘입니다.

구현 예

※위의 그림과는 반대로, 열의 선두로부터 말미를 향해 요소의 교환을 행해 갑니다

# 要素数2以上の配列aを昇順にソートする
def bubble_sort(a):
    # (要素数−1)回繰り返す
    for i in range(len(a) - 1):
        # 列の先頭2要素を最初の比較対象に選ぶ
        l = 0
        r = 1

        # rが末尾に達するまで、隣り合う要素の大小を比較する
        while r < len(a):
            # 隣り合う要素の大小が逆であれば交換する
            if a[l] > a[r]:
                a[l], a[r] = a[r], a[l]
            # 比較対象のindexをインクリメントする
            l += 1
            r += 1

참고

https://ko.wikipedia.org/wiki/버블 정렬
h tp : // Judge. 우아이즈. 아 c. jp / 온 네쥬 드게 /에서 sc 리 p 치온. jsp? 아니 d = A LDS1_2_A

선택 정렬(Selection Sort)

개요

선택 소트는 최소값을 순차적으로 찾아 가고, 미소트 부분의 선두로 이동해 가는 것으로 정렬을 실시하는 수법입니다. 평균 계산 시간, 최악 계산 시간은 모두 O($n^2$)로 불안정한(unstable) 정렬 알고리즘입니다.

구현 예

# 配列aを昇順にソートする
def selection_sort(a):
    for i in range(len(a)):
        # 最小値のindex
        min_idx = i

        # i以降の要素で最小のものを探す
        for j in range(i + 1, len(a)):
            if a[j] < a[min_idx]:
                min_idx = j

        # 発見した最小値を未ソート部分の先頭に移す
        if i != min_idx:
            a[i], a[min_idx] = a[min_idx], a[i]

참고

h tp : // Judge. 우아이즈. 아 c. jp / 온 네쥬 드게 /에서 sc 리 p 치온. jsp? D = A LDS1_2_B
https://ko.wikipedia.org/wiki/선택 정렬

병합 정렬(Merge Sort)

개요

병합 정렬은 분할 통치법 (Divide and Conquer)을 사용하여 정렬을 수행하는 방법입니다. 대상이 되는 배열을 하나의 요소가 될 때까지 분할해, 대소 관계를 비교하면서 병합을 실시하는 것으로, 최종적으로 정렬된 배열을 얻을 수 있습니다. n개의 요소를 가지는 배열의 분할에 필요한 계산량은 $O(logn)$, 병합에 필요한 계산량은 $O(n)$이므로, 병합 소트의 계산량은 $O( nlogn)$입니다. 안정적인 정렬 알고리즘이지만 일시적인 작업 저장 영역이 필요할 수 있습니다.

구현 예

# 配列aを昇順に並べ替える
def merge_sort(a):
    if len(a) == 1:
        return

    # 配列を二つに分ける
    m = len(a) // 2
    x = a[:m]
    y = a[m:]

    # 分割とマージを再帰的に行う。最終的に一つの要素まで分割された段階からマージが行われていく
    merge_sort(x)
    merge_sort(y)
    merge(x, y, a)

# 配列x, yをマージし、aにセットする
def merge(x, y, a):
    # x, yのindex
    i = 0
    j = 0

    # x, yの先頭の要素を比較し、小さい要素から順にaにセットしていく
    while i < len(x) or j < len(y):
        # xの要素を全て追加済みの場合、y[j]をセットする
        if i == len(x):
            a[i+j] = y[j]
            j += 1
        # yの要素を全て追加済みの場合、x[i]をセットする
        elif j == len(y):
            a[i+j] = x[i]
            i += 1
        # x[i]がy[j]以下の場合、x[i]をセットする
        elif x[i] <= y[j]:
            a[i+j] = x[i]
            i += 1
        # y[j]がx[i]より小さい場合、y[j]をセットする
        else:
            a[i+j] = y[j]
            j += 1

참고

h tp : // Judge. 우아이즈. 아 c. jp / 온 네쥬 드게 /에서 sc 리 p 치온. jsp? 아니 d = 아 LDS1_5_B & ぁ g =
https://ko.wikipedia.org/wiki/병합 정렬

기타(추가 예정)

쉘 정렬

빠른 정렬

힙 정렬

기수 정렬

버킷 정렬