병합 정렬

 

병합 정렬

여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬되 집합으로 만드는 방식

자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻음.

Top-Down 방식

O(n log n)

 

 

def merge(left, right):
  result=[]   # 두 개의 분할된 리스트를 병합하여 result 만듦

  while len(left) > 0 and len(right) > 0 :  # 양쪽 리스트에 원소가 남아있는 경우
    # 두 서브 리스트의 첫 원소들을 비교하여 작은 것부터 result에 추가
    if left[0] <= right[0] :
      result.append(left.pop(0))
    else :
      result.append(right.pop(0))

  if len(left) > 0 :  # 왼쪽 리스트에 원소가 남아있는 경우
    result.extend(left)
  if len(right) > 0 : # 오른쪽 리스트에 원소가 남아있는 경우
    result.extend(right)
  return result

def merge_sort(m):
  if len(m) <= 1 :    # 사이즈가 0이거나 1인 경우, 바로 리턴
    return m

  # 1. divide 부분
  mid=len(m)//2
  left=m[:mid]
  right=m[mid:]

  # 리스트의 크기가 1이 될 때까지 merge_sort 재귀 호출
  left=merge_sort(left)
  right=merge_sort(right)

  # 2. conquer 부분 : 분할된 리스트들 병합
  return merge(left, right)
  

 

merge함수에서는 left와 right 원소들을 비교해서 병합한다.

비교가 끝나고도 남은 원소는 result 리스트 뒤에 추가한다.

merge_sort함수는 병합 정렬할 m의 길이가 1과 같거나 작을 때까지 분할한다. 재귀호출을 사용한다.

가운데 mid를 기준으로 left와 right로 분할한다.

 

 

🍿 나의 풀이

 

# 병합(오름차순 정렬)
data1=list(map(int, input().split()))
data2=list(map(int, input().split()))
merge=list()

while data1 != [] and data2 != [] :
  if data1[0] > data2[0] : 
    merge.append(data2.pop(0))
  elif data1[0] < data2[0] :
    merge.append(data1.pop(0))
  else:     # 두 값이 같을 때
    merge.append(data1.pop(0))
    data2.pop(0)

# 남은 값 merge에 추가
if data1 :
  merge+=data1
else :
  merge+=data2

print(merge)

 

병합 기능만 구현해 봄.

data1과 data2가 각각 오름차순 정렬된 리스트라는 가정.

 

 

🍳 다른 사람 풀이

 

# 출처 : https://www.daleseo.com/sort-merge/

def merge_sort(arr):
    def sort(low, high) :       # 분할
        if high - low < 2 :
            return
        mid=(low+high)//2
        sort(low, mid)
        sort(mid, high)
        merge(low, mid, high)

    def merge(low, mid, high) :			# 병합
        temp=[]
        l, h=low, mid
		# 비교. 더 작은 원소를 temp에 삽입
        while l < mid and h < high :
            if arr[l] < arr[h] :
                temp.append(arr[l])
                l+=1
            else :
                temp.append(arr[h])
                h+=1
        # 남은 원소가 있다면 추가        
        while l < mid :
            temp.append(arr[l])
            l+=1
        while h < high :
            temp.append(arr[h])
            h+=1

        for i in range(low, high) :
        	# 원래 리스트 arr을 정렬. i-low를 해야 범위를 벗어나지 않음
            arr[i]=temp[i-low]	

    return sort(0, len(arr))

merge_sort([69, 10, 30, 2, 16, 8, 31, 22])			# 함수 호출

 

merge_sort함수를 호출하면 처음에 sort가 호출됨.

함수 sort에서 비교할 인덱스 범위를 정한다. 길이가 1이 될 때 까지 분할 후 merge함수 호출

merge함수에서 병합한다. temp에 담은 원소를 arr에 담는다(정렬)

다소 복잡한 풀이다.

 

 

 

 

참고. SW expert academy