병합 정렬, 퀵 정렬 (Python) 코드

병합정렬

n = int(input())
arr = list(map(int, input().split()))
merged_arr = [0] * n

def merge_sort(low, high):
    if low < high:
        mid = (low + high) // 2
        merge_sort(low, mid)
        merge_sort(mid+1, high)
        merge(low, mid, high)


def merge(low, mid, high):
    i, j = low, mid + 1
    k = low

    while i <= mid and j <= high:
        if arr[i] <= arr[j]:
            merged_arr[k] = arr[i]
            i += 1
            k += 1
        else:
            merged_arr[k] = arr[j]
            j += 1
            k += 1
    
    while i <= mid:
        merged_arr[k] = arr[i]
        k += 1
        i += 1

    while j <= high:
        merged_arr[k] = arr[j]
        k += 1
        j += 1
    
    for k in range(low, high+1):
        arr[k] = merged_arr[k]

merge_sort(0, n - 1)

for elem in arr:
    print(elem, end=" ")

 

퀵 정렬

n = int(input())
arr = list(map(int, input().split()))

def partition(arr, low, high):
    i = low - 1

    for j in range(low, high):
        if arr[j] < arr[high]:
            i += 1
            swap(i, j)
    
    swap(i+1, high)
    return i+1

def quick_sort(arr, low, high):
    if low < high:
        pos = partition(arr, low, high)
        quick_sort(arr, low, pos - 1)
        quick_sort(arr, pos + 1, high)
   

def swap(a, b):
    arr[a], arr[b] = arr[b], arr[a]


quick_sort(arr, 0, len(arr) - 1)
for i in range(len(arr)):
    print(arr[i], end=" ")