[지혜/week2] 분할정복과 퀵정렬, 병합정렬

분할 정복 이란?

분할정복 알고리즘은 문제를 나눌 수 없을 떄까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답은 얻는 알고리즘이다.

알고리즘을 설계하는 요령

(1) 분할(Dicide) : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다.

(2) 정복(Conquer) : 나누어진 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다.

(3) 결합(Combine) : Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다.

• 분할정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할정복 알고리즘의 효율성을 깎아내릴 수 있다.

퀵정렬과 병합정렬

1. 퀵정렬

• 교환정렬의 일종이며 분할-정복법(divide and conquer)에 근거한다.

• 정렬할 리스트를 두개로 분할하고 정렬하는 방법이다.

• 축(pivot)값을 기준으로 정렬하는데, 축값을 중심으로 축값보다 큰 값은 오른쪽 리스트에 작은 값은 왼쪽리스트로 이동시킨다. (첫번째의 데이터를 축값으로 한다.)

• 오른쪽 리스트와 왼쪽 리스트부분은 독립적인 단위로 정렬하여 오른쪽 리스트부분에 대한 새로운 분할 축값을 선택하여 두 부분으로 분리하고, 왼쪽 리스트부분 역시 새로운 축값을 선택하여 두 부분으로 분리하는 과정을 반복하는데 리스트들은 재귀적 방법으로 각각 재배열하는 방식이다.

• 각 분할 자료개수가 1이 되면 정렬은 완료된다.

코드예시) https://fistpark.tistory.com/entry/%ED%80%B5%EC%A0%95%EB%A0%ACQuick-Sort%EC%9D%B4%EB%9E%80

2. 병합정렬

• 리스트의 길이가 1이 될때까지 반으로 잘게 나눈다.-> 분할(Divide)

• 다 나누어 졌다면, 데이터를 합치는데(Merge), 정렬하면서 합친다.

귀류법

수학적 귀납법과 반복문 불변식

• 2019 14