[백준, BOJ 2751] 수 정렬하기 2 (python)

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

---

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

728x90

 

예제 입력 1

5
5
4
3
2
1

예제 출력 1

1
2
3
4
5

---

sorted 함수 사용

import sys

n = int(input())
num = [int(sys.stdin.readline()) for _ in range(n)]
sorted_num = sorted(num)

for i in sorted_num:
    print(i)

Merge sort

import sys

# 두개의 리스트를 입력 받는다.
# left와 right 리스트는 각자 정렬된 형태이다.
# 두 리스트를 합치며, 정렬된 하나의 리스트로 만들어 반환한다.
def merge(left, right):
    merge_arr = []
    i = j = 0
    
    # left, right 앞에서 부터 비교해서 작은 것을 append 해줌
    # left나 right 둘 중 하나의 리스트를 모두 append할 때까지
    while (i < len(left)) and (j < len(right)):
        if left[i] < right[j]:
            merge_arr.append(left[i])
            i += 1
        else:
            merge_arr.append(right[j])
            j += 1
    # 남은 리스트의 남은 원소를 마저 추가 해줌.
    merge_arr.extend(left[i:])
    merge_arr.extend(right[j:])
    return merge_arr
        
# 각 len이 1이 될 때까지 리스트를 반으로 쪼개준다.
# len이 1인 상태의 리스트는 정렬됐다고 할 수 있다.
# 이 정렬된 상태의 리스트 2개를 merge 함수를 통해 하나의 정렬된 리스트로 만들어준다.
# 재귀를 통해 다시 n 길이의 하나의 리스트가 될 때까지 수행해준다.
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    leftArr = arr[:mid]
    rightArr = arr[mid:]
    leftArr = merge_sort(leftArr)
    rightArr = merge_sort(rightArr)
    return merge(leftArr, rightArr)

n = int(input())
num = [int(sys.stdin.readline()) for _ in range(n)]
sorted_num = merge_sort(num)

for i in sorted_num:
    print(i)

Quick sort (시간 초과)

퀵 정렬은 최악의 경우 $O(N^{2})$이다.

그래서 한 70~80% 정도 돌아갔을 때 시간 초과가 뜬다.

따라서 퀵 정렬은 알고리즘 문제에서 사용하지 않는 것이 좋다고 한다.

import sys

def quick_sort(arr, left, right):
    if (left >= right):
        return
    i, j = left, right
    pivot = arr[(left + right) // 2]
    
    while (i <= j):
        while (arr[i] < pivot):
            i += 1
        while (arr[j] > pivot):
            j -= 1
        if (i <= j):
            t = arr[i]
            arr[i] = arr[j]
            arr[j] = t
            i += 1
            j -= 1
            
    quick_sort(arr, left, j)
    quick_sort(arr, i, right)

n = int(input())
num = [int(sys.stdin.readline()) for _ in range(n)]
quick_sort(num, 0, n - 1)

for i in num:
    print(i)