분할 정복 알고리즘의 분류

분할 정복 알고리즘 

1. 합병 정렬, 최근점 점의 쌍 찾기 

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

2. 퀵정렬

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

3.선택 문제 알고리즘

*문제가 2개로 분할, 그중에 1개의 부분 문제는 고려할 필요 없으며

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

 

합병정렬 알고리즘 (Merge Sort)

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

1.n개의 숫자들을 n/2개씩 2개의 부분 문제로 분할 함 

2. 각각의 부분문제를 재귀적으로 합병 정력함

3. 2개의 정렬된 부분을 합병하여 정렬(정복)함

 

퀵 정렬(Quick Sort)

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

1, 피봇(Pivot)이라 일컫는 배열의 원소(숫자)를 기준으로 피봇보다 작은 

    숫자들을 왼편으로, 피봇보다 큰 숫자들은 오른편에 위치하도록 분할하고 피봇을 그 사이에 놓음

2. 분할된 부분 문제들에 대해서도 위와 동일한 과정을 재귀적으로 수행하여 정렬함