백준(baekjoon) 2751번: 수 정렬하기 2 (실버 5, 파이썬 PYTHON) - 정렬

문제

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

 

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

2751번: 수 정렬하기 2

 

N=int(sys.stdin.readline())
num_list=[]

for _ in range(N):
  num=int(sys.stdin.readline())
  num_list.append(num)

def Merge(arr,start,mid,end):
  sort=[]
  i,j=start,mid+1
  while(i<=mid and j<=end):  
    if(arr[i]<arr[j]):   
      sort.append(arr[i]) 
      i+=1 
    else: 
      sort.append(arr[j]) 
      j+=1  
  if(i<=mid):  
    while(i<=mid):
      sort.append(arr[i])
      i+=1 
  elif(j<=end): 
    while(j<=end):
      sort.append(arr[j])
      j+=1 
  num_list[start:end+1]=sort 

def Merge_sort(arr,start,end):
  if(start>=end):
    return 
  mid=(start+end)//2
  Merge_sort(arr,start,mid) 
  Merge_sort(arr,mid+1,end)
  Merge(arr,start,mid,end)  

Merge_sort(num_list,0,N-1)

for x in num_list:
  print(x)

 

※ 정렬

 

 

이 문제는 입력이 최대 1,000,000개가 들어오므로 삽입정렬같은 복잡도가 O(n^2) 인 알고리즘으로 풀면 시간초과가 나게 된다. O(nlogn) 의 복잡도를 가지는 병합 정렬로 이 문제를 풀어보았다.

 

● Merge_sort 함수를 재귀적으로 호출해준다. 주어진 배열 범위의 요소들을 계속 2등분으로 나누어준 뒤 나누어진 배열들을 각각 merge해주는 단계를 재귀적으로 거치게 된다. 주어진 배열 요소가 하나뿐이면 merge를 진행 할 필요가 없으므로 return 해준다.

 

● Merge 함수에서는 주어진 배열을 두 부분으로 나누어 합병을 진행하게 된다. 이 때 새로운 배열 sort 를 만들어 준 뒤 두 부분으로 나누어진 배열의 요소들을 비교하게 된다. 두 부분의 배열 중 어느 한 배열의 요소가 sort 안에 다 들어가기 전까지 각 배열의 요소 중 작은 수 부터 sort 에 append 해준다.

 

● 그 후, 아직 sort에 들어가지 않은 요소가 존재하는 쪽의 배열에서 남은 요소들을 차례대로 sort 에 모두 append 해준다.

 

● 주어진 배열 범위에 sort를 그대로 대입해주면 합병 정렬이 끝나게된다!!

 

밑 사이트에 합병정렬의 과정이 매우 자세하게 나타나 있다. 참고!!!

 

 

결과

 

 

♣ 참고: 병합 정렬

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

합병 정렬 - 위키백과, 우리 모두의 백과사전

https://www.daleseo.com/sort-merge/

[알고리즘] 병합 정렬 - Merge Sort (Python, Java)