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

안녕하세요? 주니하랑 입니다.

오늘은 자료구조와 알고리즘의 알고리즘에서 병합정렬에 대해 공부 해 보도록 하는 것이에요.

병합 정렬은 분할 정복에 대표적인 정렬 알고리즘인 것이에요. 분할 정복에 대해 잘 모르신다면 Dynamic Programming(동적 계획법)& Divide and Conquer(분할 정복)에 관심을 주세요!

소스 코드에 대해서 확인 하고 싶으신 분들께서는 주니하랑의 Git hub에 관심을 주세요!

 

 

 

---

 

 

 

📌 병합 정렬 (Merge sort)

---

 

병합 정렬은 재귀용법을 활용한 알고리즘 친구 중 하나인 것이에요.

먼저, 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나누는 작업을 합니다!

그런 뒤, 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬을 하는 것이에요.

마지막으로 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병하면 되는 알고리즘이랍니다!

 

잘 이해가 되지 않으신다면 이 곳을 한번 봐보셔요!

 

 

출처 : 위키피디아

 

 

 

📌 알고리즘 이해

---

Data가 네 개 일때, (Data 개수에 따라 복잡도가 떨어지는 것은 아니다. 따라서 네 개로 바로 Logic을 이해해보고자 한다.)

1. 예: data_list = [1, 9, 3, 2]
   • 먼저 [1, 9], [3, 2]로 쪼갠다.
   • 다시 앞 부분은 [1], [9]로 쪼갠다.
   • 그런 뒤 앞과 뒤의 값을 비교하여 작은 값을 앞으로 오도록 하여 합친다. [1, 9]
   • 뒤 부분 역시 [3], [2]로 쪼갠다.
   • 그런 뒤 앞과 두의 값을 비교하여 작은 값을 앞으로 오도록 하여 합친다. [2, 3]
   • 이제 앞, 뒤 배열 모두를 합친다.
     • 1 < 2 이기에 [1]
     • 9 > 2 이기에 [1, 2]
     • 9 > 3 이기에 [1, 2, 3]
     • 9 혼자 남았기 때문에 [1, 2, 3, 9]

 

 

 

 

📌 알고리즘 구현

---

 

1. merge_split 함수 만들기
   • 만약 리스트 개수가 한개라면 해당 값 반환
   • 그렇지 않다면, 리스트를 앞과 뒤로 두 개 나눈다.
   • left = merge_split(앞)
   • right = merge_split(뒤)
   • merge(left, right)
2. merge 함수 만들기
   • 리스트 변수 하나 만들기 (sorted)
   • left_index, right_index = 0
   • while left_index < len(left) or right_index < len(right):
     • 만약 left_index나, right_index가 이미 left 또는 right 리스트를 다 순회했다면, 그 반대쪽 Data를 넣고, 해당 Index 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

 

 

 

 

📌 알고리즘 분석

---

 

알고리즘 분석은 사실 쉽지 않은 것이에요. 

먼저 몇 단계 깊이까지 만들어지는지를 depth라고 하고, i로 놓을 것이에요. 그런 뒤 맨 윗단계는 0으로 놓을게요.

아래 그림에서 n/$2^2$를 2단계 깊이라고 가정했을 때, 각 단계에 있는 하나의 Node안에 리스트 길이는 n/$2^2$가 되는 것이에요.

각 단계에는 $2^i$ 개의 Node가 있는 셈이에요. 쉽게 말해서 아래 그림에서 n이 0단계 n/2가 1단계 n/$2^2$가 2단계 일 때, 2단계에서는 $2^2$ 개 즉 4개의 Node가 있는 것이고, 1단계에서는 $2^1$개 즉 2개의 Node가 있는 것이에요.

따라서 각 단계는 항상 $2^i * \frac { n }{ 2^i } = O(n)$인 것이고, 단계는 항상 $log_2 n$개 만큼 만들어지는 것이에요.

결국 시간 복잡도는 O($log n$)이고, 2는 역시 상수이기 때문에 삭제가 되는 것이에요.

따라서 단계별 시간 복잡도 O(n) * O($log n$) = O($n log n$)이 되는 것이에요.

 

반응형

 

 

 

 

---

 

주니하랑의 글이 마음에 드셨나요? 구독과 공감! 그리고, 댓글 그리고 방명록은 주니하랑에게 많은 힘이 됩니다