[알고리즘] 병합 정렬 (merge sort)

1. 병합 정렬 (merge sort)

• 재귀용법을 활용한 정렬 알고리즘
  1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
  3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

이 사이트에서 시뮬레이션을 확인하자!

2. 알고리즘 이해

데이터가 네 개 일때 (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.)
예: data_list = [1, 9, 3, 2]

• 먼저 [1, 9], [3, 2] 로 나누고
  - 다시 앞 부분은 [1], [9] 로 나누고
  - 다시 정렬해서 합친다. [1, 9]
• 다음 [3, 2] 는 [3], [2] 로 나누고
  - 다시 정렬해서 합친다 [2, 3]
• 이제 [1, 9] 와 [2, 3]을 합친다.
  - 1 < 2 이니 [1]
  - 9 > 2 이니 [1, 2]
  - 9 > 3 이니 [1, 2, 3]
  - 9 밖에 없으니, [1, 2, 3, 9]

3. 알고리즘 구현

split()

• 만약 리스트 갯수가 한개이면 해당 값 리턴
• 그렇지 않으면, 리스트를 앞뒤, 두 개로 나누기
• left = mergesplit(앞)
• right = mergesplit(뒤)
• merge(left, right)

merge()

• 리스트 변수 하나 만들기 (sorted)
• left_index, right_index = 0
• while left_index < len(left) or right_index < len(right):
  - 만약 left_index 나 right_index 가 이미 left 또는 right 리스트를 다 순회했다면, 그 반대쪽 데이터를 그대로 넣고, 해당 인덱스 1 증가

  if left[left_index] < right[right_index]:
    sorted.append(left[left_index])
    left_index += 1
  else:
    sorted.append(right[right_index])
    right_index += 1
  

프로그래밍 연습

def mergeSort(dataList): # 작게 split 후에 merge
    if len(dataList) <= 1:
        return dataList
    
    mid = int(len(dataList)/2)
    leftList = mergeSort(dataList[:mid]) # 재귀적으로 split
    rightList = mergeSort(dataList[mid:]) # 재귀적으로 split
    
    return merge(leftList,rightList)
    
def merge(leftList, rightList): # lp와 rp를 한 칸씩 옮기면서 크기 비교해가며 leftList와 rightList 병합
    merged = list()
    lp, rp = 0, 0 # pointer: 인덱스 번호
    
    # case 1: leftList와 rightList 모두 아직 남아있을 때
    while len(leftList) > lp and len(rightList) > rp:
        if leftList[lp] > rightList[rp]:
            merged.append(rightList[rp])
            rp += 1
        else:
            merged.append(leftList[lp])
            lp += 1
        
        
    # case 2: leftList만 남아있을 때
    while len(leftList) > lp:
        merged.append(leftList[lp])
        lp += 1
        
        
    # case 3: rightList만 남아있을 때
    while len(rightList) > rp:
        merged.append(rightList[rp])
        rp += 1
    
    return merged

코드 이미지

테스트

4. 알고리즘 분석

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기