백준 2751 - 수 정렬하기 2 (파이썬)

Answer

Merge sort

import sys
input = sys.stdin.readline

n = int(input())
a = []

for _ in range(n):
    a.append(int(input()))

def merge_sort(list, s, e):
    length = e - s
    if length <= 1:
        return [list[s]]
        
    mid = (e - s) // 2
    
    leftList = merge_sort(list, s, s + mid)
    rightList = merge_sort(list, s + mid, e)
    
    return merge(leftList, rightList)

def merge(leftList, rightList):
    result = []
    i = 0
    j = 0
    while (i < len(leftList)) and (j < len(rightList)):
        if leftList[i] < rightList[j]:
            result.append(leftList[i])
            i += 1
        else:
            result.append(rightList[j])
            j += 1
    
    while i < len(leftList):
        result.append(leftList[i])
        i += 1
        
    while j < len(rightList):
        result.append(rightList[j])
        j += 1
    
    return result

for i in merge_sort(a, 0, len(a)):
    sys.stdout.write(str(i)+'\n')

Answer2

Heap sort

import sys
input = sys.stdin.readline

def heap_sort(a):
    n = len(a)
    
    for i in range(n // 2 - 1, -1, -1):
        heapify(a, i, n)

    for i in range(n - 1, 0, -1):
        a[0], a[i] = a[i], a[0]
        heapify(a, 0, i)
        
    return a

def heapify(a, i, s):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < s and a[l] > a[largest]:
        largest = l
    if r < s and a[r] > a[largest]:
        largest = r
    if largest != i:
        a[largest], a[i] = a[i], a[largest]
        heapify(a, largest, s)

n = int(input())
answer = []
for _ in range(n):
    answer.append(int(input()))

for i in heap_sort(answer):
    sys.stdout.write(str(i) + '\n')

Answer3

Quick sort

import sys
input = sys.stdin.readline

def quick_sort(arr):
    def sort(low, high):
        if high <= low:
            return

        mid = partition(low, high)
        sort(low, mid - 1)
        sort(mid, high)

    def partition(low, high):
        pivot = arr[(low + high) // 2]
        while low <= high:
            while arr[low] < pivot:
                low += 1
            while arr[high] > pivot:
                high -= 1
            if low <= high:
                arr[low], arr[high] = arr[high], arr[low]
                low, high = low + 1, high - 1
        return low

    return sort(0, len(arr) - 1)

n = int(input())
answer = []
for _ in range(n):
    answer.append(int(input()))
    
quick_sort(answer)

for i in answer:
    sys.stdout.write(str(i) + '\n')

pypy로 제출하셔야 합니다