[SWEA 1966 python] 숫자를 정렬하자

방법 1) bubble sort

def bubble_sort(lst):
    for i in range(1, len(lst)):
        for j in range(len(lst) - i):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]

    return lst

if __name__=='__main__':
    T = int(input())

    for t in range(1, T + 1):
        N = int(input())
        lst = list(map(int, input().split()))

        bubble_sort(lst)

        print('#{}'.format(t), end=' ')
        print(*lst, sep=' ')

방법 2) selection sort

def selection_sort(lst):
    for i in range(len(lst) - 1):
        for j in range(i + 1, len(lst)):
            if lst[i] > lst[j]:
                lst[i], lst[j] = lst[j], lst[i]

    return lst

if __name__=='__main__':
    T = int(input())

    for t in range(1, T + 1):
        N = int(input())
        lst = list(map(int, input().split()))

        selection_sort(lst)

        print('#{}'.format(t), end=' ')
        print(*lst, sep=' ')

방법 3) merge sort

def merge_sort(lst, l, r):
    if r - l <= 1:
        return

    c = (l + r) // 2

    merge_sort(lst, l, c)
    merge_sort(lst, c, r)

    l_ptr = l
    r_ptr = c
    tmp_lst = []
    while l_ptr < c and r_ptr < r:
        if lst[l_ptr] < lst[r_ptr]:
            tmp_lst.append(lst[l_ptr])
            l_ptr += 1
            continue
        else:
            tmp_lst.append(lst[r_ptr])
            r_ptr += 1

    while l_ptr < c:
        tmp_lst.append(lst[l_ptr])
        l_ptr += 1

    while r_ptr < r:
        tmp_lst.append(lst[r_ptr])
        r_ptr += 1

    for tmp_i, i in enumerate(range(l, r)):
        lst[i] = tmp_lst[tmp_i]

    return lst

if __name__=='__main__':
    T = int(input())

    for t in range(1, T + 1):
        N = int(input())
        lst = list(map(int, input().split()))

        merge_sort(lst, 0, len(lst))

        print('#{}'.format(t), end=' ')
        print(*lst, sep=' ')