정렬 알고리즘

선택 정렬 (Selection Sort)

• 최소값을 선택하여 정렬하는 알고리즘

def selection_sort(a):
    n = len(a)
    for i in range(0, n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]

 

삽입 정렬 (Insert Sort)

• 정해진 위치를 찾아서 삽입하는 알고리즘

def insert_sort(a):
    n = len(a)
    for i in range(1, n):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key

 

버블 정렬 (Bubble Sort)

• 변경 여부에 따라 버블처럼 정렬하는 알고리즘

def bubble_sort(a):
    n = len(a)
    while True:
        changed = False
        for i in range(0, n-1):
            if a[i] > a[i + 1] :
                a[i], a[i + 1] = a[i + 1], a[i]
                changed = True
        if changed == False:
            return

 

병합 정렬 (Merge Sort)

• 중간값을 기준으로 정렬하여 합치는 알고리즘

def merge_sort(a):
    n = len(a)
    if n <= 1:
    return

    mid = n // 2
    g1 = a[:mid]
    g2 = a[mid:]
    merge_sort(g1)
    merge_sort(g2)

    ia, i1, i2 = 0, 0, 0
    while i1 < len(g1) and i2 < len(g2):
    if g1[i1] < g2[i2]:
        a[ia] = g1[i1]
        ia += 1
        i1 += 1
    else:
        a[ia] = g2[i2]
        ia += 1
        i2 += 1

    while i1 < len(g1):
    a[ia] = g1[i1]
    ia += 1
    i1 += 1
    while i2 < len(g2):
    a[ia] = g2[i2]
    ia += 1
    i2 += 1

 

퀵 정렬 (Quick Sort)

• 피벗값을 기준으로 나누어서 정렬하는 알고리즘

def quick_sort_sub(a, start, end):
    if end - start <= 0:
    return

    pivot = a[end]
    i = start
    for j in range(start, end):
    if a[j] <= pivot:
        a[i], a[j] = a[j], a[i]
        i += 1
    a[i], a[end] = a[end], a[i]

    quick_sort_sub(a, start, i - 1)
    quick_sort_sub(a, i + 1, end)

def quick_sort(a):
    quick_sort_sub(a, 0, len(a) - 1)