[TIL] 정렬

버블정렬

def bubble_sort(a: MutableSequence) -> None:
    n = len(a)

    for i in range(n - 1):
        for j in range(n - 1, i, -1):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]

 

단순 선택 정렬

def selection_sort(a: MutableSequence) -> None:
    n = len(a)
    
    for i in range(n - 1):
        min  = i
        for j in range(i+1, n):
            if a[j] < a[min]:
                min = j
        a[i], a[min] = a[min], a[i] #정렬할 부분에서 맨 앞의 원소와 가장 작은 원소를 교환

 

단순 삽입 정렬

def insertion_sort(a: MutableSequence) -> None:
    n = len(a)

    for i in range(1, n):
        j = i
        tmp = a[i]
        while j > 0 and a[j - 1] > tmp:
            a[j] = a[j - 1]
            j -= 1
        a[j] = tmp