알고리즘 공부 - 분할 정복 알고리즘, 합병(merge) 정렬, 퀵(quick) 정렬

분할 정렬 알고리즘이란?

주어진 문제의 입력을 분할하여 문제를 해결 = 정복하는 알고리즘

 

분할된 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하여 이들의 해를 취합하여 원래 문제의 해를 얻음

이때 분할된 입력에 대한 문제를 부분 문제라고 함

 

만약 입력 크기가 n이고 더이상 분할할수 없는 수준까지 갈려면 n/2를 반복함으로 결국 log n 이 된다

 

분할 정복 알고리즘의 분류

합병 정렬

문제가 a개로 분할되고, 부분문제의 크기가 1/b로 감소하는 알고리즘

퀵 정렬

문제가 2개로 분할되고, 부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘

이진 탐색

문제가 2개로 분할되나, 그중에 1개의 부분 문제는 고려할 필요 없이 부문문제의 크기가 1/2로 감소하는 알고리즘

선택 문제 알고리즘

문제가 2개로 분할되나, 그중에 1개의 부분 문제는 고려할 필요가 없으며, 부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘

삽입 정렬

부분 문제의 크기가 1, 2개씩 감소하는 알고리즘

 

합병 정렬(merge sort)

입력이 2개의 부분 문제로 분할되고, 부분 문제의 크기가 1/2로 감소하는 분할 정복 알고리즘

 

기본 매커니즘

mergeSort(A, p, q)

if (p < q)

k = (p+q)/2

mergeSort(A, p, k)

mergeSort(A, k+1, q)

A[p] ~ A[k], A[k+1] ~ A[q]를 합병

 

시간복잡도

n * log n

층수 * n = log n * n = O(n * log n)

 

퀵 정렬

문제를 2개의 부분 문제로 분할 한 뒤, 각 부분 문제의 크기가 일정하지 않은 형태의 분할 정복 알고리즘

 

기본 매커니즘

quickSort(A, left, right)

if (left < right)

pivot = A's position <=> left

left = pivot을 제외한 값들을 정렬 

piviot을 left+1부터 오른쪽으로 가면서 큰수 바로 앞에 배치함

quickSort(A, left, p-1) // p = 기존의 A의 위치

quickSort(A, p+1, right)

 

시간복잡도

최악의 경우 n*n이 되기 때문에 상황을 보며 사용해야 한다