[ 병합 정렬 ] 알고리즘

 

 

1.  개념

 

      병합 정렬 : 분할되어 있는 데이터 배열을 하나로 합치면서 정렬하는 것

   

        * 시간 복잡도 : O(nlogn)

 

 

      병합 정렬 방법 -  1 ) 데이터 배열을 분할하고  2 ) 다시 병합하면서 정렬하는 것

 

        -  초기 설정

           

            데이터를 하나씩 분할해준다 - 재귀함수 이용

 

            각각의 데이터 배열 요소의 개수 한 개가 될 때까지 데이터 배열을 반으로 쪼개준다

            재귀함수의 종료 조건 : 데이터 배열의 요소의 개수가 한 개가 될 때 

      

         - 병합 정렬 과정 : 근접한 데이터와 병합하면서 정렬해준다 

            

             재귀함수가 종료 조건을 만족한 후, 재귀함수 호출 코드 뒤에 있던 배열 병합 코드가 수행된다

                  

              근접한 데이터 배열과 병합해준다

         

              ( 1 ) 각 데이터 배열의 첫번째 데이터를 포인터로 가르킨다

                      

              ( 2 ) 포인터로 지정된 데이터끼리 비교해준다

                   둘 중 더 작은 데이터 : 병합 배열에 넣어준다 / 데이터가 포함된 배열의 포인터를 오른쪽으로 한 칸 옮겨준다.

                   둘 중 더 큰 데이터 : 그대로

                     

     

 

 

2.  문제 풀이

 

# 1  수 정렬하기2 - 백준 2751번

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

2751번: 수 정렬하기 2

 

 

import sys 
input = sys.stdin.readline

# 병합 정렬 함수
def merge_sort(s,e):
    
    ## 초기 설정 : 데이터 배열 분할 - 각각의 데이터 배열의 요소 개수가 하나가 될 때까지 배열을 분할 ##
    
    # 조건 : 데이터 배열의 요소의 개수가 하나가 될 때까지
    if e-s < 1 : return
    
    # 분할 지점 m 설정
    m = int(s+(e-s)/2)
    
    # 재귀함수 이용해서 조건 만족할 때까지 데이터 배열 분할
    merge_sort(s,m)
    merge_sort(m+1,e)
    
        
    ## 데이터 병합 과정 - 근접한 두 배열 병합하면서 정렬 ##
    ## 조건을 만족한 뒤 재귀함수 stack에서 하나씩 pop되면서 수행됨 - 가장 마지막으로 호출된 재귀함수부터 pop ##
    
    for i in range(s,e+1):
        tmp[i] = A[i]
    
    k = s
    # 앞쪽 배열 시작 지점(포인터)
    index1 = s
    # 뒤쪽 배열 시작 지점(포인터)
    index2 = m+1
    
    
    # 포인터가 배열의 마지막 요소를 가르킬 때까지 반복
    while index1 <= m and index2 <= e:
        
        # 두 포인터가 가르키는 데이터끼리 비교 
        # 더 작은 데이터 : 병합 배열(A)에 넣기 / 데이터가 포함된 배열의 포인터 오른쪽으로 옮기기 
        
        if tmp[index1] > tmp[index2]:
            A[k] = tmp[index2]
            k += 1 
            index2 += 1
            
        else:
            A[k] = tmp[index1]
            k += 1
            index1 += 1
    
    # 한쪽 그룹이 다 병합 배열에 들어간 뒤 나머지 그룹 정리
          
    while index1 <= m:
        A[k] = tmp[index1]
        k += 1
        index1 += 1
    
    while index2 <= e:
        A[k] = tmp[index2]
        k += 1
        index2 += 1


## 입출력 ##

N = int(input())
A = [0] * int(N+1)   
tmp = [0] * int(N+1)

for i in range(1,N+1):
    A[i] = int(input())

merge_sort(1,N)

for i in range(1,N+1):
    print(str(A[i])+ '\n')

 

 

 

# 2  버블 정렬 프로그램 2 - 백준 1517번

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

1517번: 버블 소트

좀 더 공부하고 풀겠음...