[Do-it! 코딩 테스트-기초편] 020. 수 정렬하기 2

문제

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

2751번: 수 정렬하기 2

---

접근

데이터 크기: 1,000,000

시간 제한: 2초

정렬 알고리즘 중에 시간 복잡도가 O(N logN) 인 알고리즘 사용

heap sort 와 merge sort

 

quick sort의 평균 시간 복잡도가 O(N logN)이라고는 하지만, 최악의 경우를 고려하면 느린 정렬에 속하기 때문에 시간 초과이다.

---

코드

import sys

def merge_sort(arr):
    def sort(left, right):
        if (right - left) < 2:
            return
        mid = (right + left) // 2
        sort(left, mid)
        sort(mid, right)
        merge(left, mid, right)

    def merge(left, mid, right):
        temp = []
        l_pointer = left
        r_pointer = mid

        while l_pointer < mid and r_pointer < right:
            if arr[l_pointer] < arr[r_pointer]:
                temp.append(arr[l_pointer])
                l_pointer += 1
            else:
                temp.append((arr[r_pointer]))
                r_pointer += 1

        while l_pointer < mid:
            temp.append(arr[l_pointer])
            l_pointer += 1

        while r_pointer < right:
            temp.append(arr[r_pointer])
            r_pointer += 1

        for i in range(left, right):
            arr[i] = temp[i - left]

    return sort(0, len(arr))

N = int(sys.stdin.readline())
li = [0] * N
for i in range(N):
    li[i] = int(sys.stdin.readline())

merge_sort(li)

for i in range(N):
    sys.stdout.write(str(li[i]) + '\n')

---

설명

---

알고리즘

2023.11.02 - [분류 전체보기] - [알고리즘] merge sort

[알고리즘] merge sort