Sorting - (6)

Merge Sort

Divide and Conquer 방식을 이용하여, 데이터 분할 및 정렬하여 합치는 알고리즘.
시간 복잡도 => O(nlogn)

• 가장 작은 데이터 집합 부터 하나씩 정렬해가면서 => 전체 정렬

ex)
1. 42 32 24 60
2. 42 32 | 24 60
3. 32 42 | 24 60
4. 24 32 42 60

투 포인터를 이용하면 쉽게 정렬이 가능하다.

수 정렬하기(백준 2751번, 시간 제한: 2초)

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

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

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

입력 예시
5
5
4
3
2
1

출력 예시
1
2
3
4
5

코드 예시

import sys
input = sys.stdin.readline
def merge_sort(start,end):
    if(start<end): # 나눌 수 있을 때까지 분할
        middle=(start+end)//2
        merge_sort(start,middle)
        merge_sort(middle+1,end)
        merge(start,middle,end)

# 투 포인터를 이용하여 정렬.(두 배열 씩 짝짓기)
def merge(start,middle,end):
   i=start
   k=start
   j=middle+1
   while i<=middle and j<=end :
       if list[i]<list[j]:
           sorted[k]=list[i]
           k+=1
           i+=1
       else:
           sorted[k]=list[j]
           j+=1
           k+=1
   while i<=middle:
       sorted[k]=list[i]
       k+=1
       i+=1
   while j<=end:
       sorted[k]=list[j]
       k+=1
       j+=1
   for s in range(start,end+1):
       list[s]=sorted[s]

N=int(input())
list=[0]*int(N+1)
sorted=[0]*int(N+1)
for i in range(0,N):
   list[i]=int(input())
merge_sort(0,N-1)
for i in range(0,N):
   print(list[i],end="\n")

N의 범위가 1,000,000 이다. 때문에 O(nlogn) 시간 복잡도로 풀면 된다. => Merge Sort 를 사용하자.