코딩테스트 - 패스트캠퍼스 챌린지 12일차

수강한 강의
Chapter 15 고급 정렬 알고리즘
- 병합 정렬

학습 후기
병합 정렬 or 합병 정렬(merge sort)
비교 기반 정렬 알고리즘이며 분할 정복 알고리즘의 하나이다.
아래 위키피디아 이미지를 보며 합병 정렬이 어떻게 진행되는지 이해해본다.

합병 정렬 예시

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

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

병합 정렬은 다음과 같이 작동한다.
1. 분할(divide): 정렬되지 않은 리스트를 잘라 각각 하나의 원소만 포함하는 n개의 부분 리스트로 분할한다.
2. 정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
3. 결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시 배열에 저장된다.
4. 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다.

Merge Sort를 구현하기 전에 먼저 문장으로 필요한 걸 적어본다.
1. 데이터를 나누는 함수 split
  1-1. 데이터 길이가 1보다 작거나 같으면 return
  1-2. 데이터 길이가 1보다 크면 leftArray, rightArray로 나눈다.
2. 데이터를 정렬하며 합치는 함수 merge
  2-1. leftArray, rightArray를 파라미터로 받는다.
  2-2. 두 배열에 포인터를 사용하여 크기를 비교하며 하나의 배열로 합친다.
    2-2-1. leftArray, rightArray 둘 다 있을 때, 포인터에 해당하는 데이터 값 비교하여 작은 값을 임시 배열에 담고 포인터는 해당 배열의 다음 값을 지목.
    2-2-2. leftArray만 남았을 때, leftArray는 이미 정렬된 값이므로 임시 배열 뒤에 붙임
    2-2-3. rightArray만 남았을 때, rightArray는 이미 정렬된 값이므로 임시 배열 뒤에 붙임

병합 정렬의 시간 복잡도는 O(n log n)이다. 전체 데이터를 각 단계별로 분할할 때 둘로 나뉘기 때문에 단계는 항상 밑이 2인 log n이다. 각 단계마다 비교는 데이터 n개의 크기만큼 하기 때문에 시간 복잡도는 O(n) * O(log n) = O(n log n)으로 표현된다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.