분할 정복법

분할, 정복, 합병은?
즉, 문제를 작게 분할해서 이렇게 분할한 동일한 문제를 해결하기 때문에 순환적(recursion, 재귀)해결하고 이 해결한 값들을 다시 비교하여 답을 도출하는 것

Merge sort

단점 : 합병정렬을 하기 위해서는 배열 하나 더 필요 (tmp)

첫번째 while문의 종료는 분할된 데이터 중 하나는 정렬이 완료되었음을 의미한다. 이 첫번재 반복문이 종료되었을 때 두번째, 세번째 while문중에 하나가 실행되는데, 두번째 while문은 앞쪽의 데이터가 남아있을 때 실행되고 세번째 while문은 뒤쪽의 데이터가 남아있을 때 실행된다.
정렬이 다 된 후에는 원래 data가 들어있었던 배열에 다시 넣어주는 작업으로 for문을 실행한다.

Merge sort의 시간복잡도

n은 merge하는 시간

분할정복법을 따르는 시간복잡도는 for문 등 반복횟수로 계산하지 않고 위와 같이 시간복잡도의 순환식을 세워 수학적으로 풀어 계산한다. 따라서 merge sort의 시간복잡도는 O(n logn)

Quick sort

Quick sort의 분할정복법에서 분할은 merge sort와 조금 다르다.
단순히 절반으로 나누어 분할하는 merge sort와는 다르게 quick sort는 pivot이라는 기준점을 가지고 분할을 한다.
(여기서는 마지막 값을 pivot으로 기준 잡았다.)