Chapter 04 -퀵정렬

분할 정복 전략

-알고리즘이라기 보다는 문제를 풀기위한 방법론에 가깝다.

-순서 1. 가장 간단한 경우로 기본단계를 찾는다

 순서 2. 주어진 문제를 작게 줄여서 기본단계가 되도록 만드는 법을 찾아 낸다.

-활용 예 ) 재귀함수로 합계구하기 

                1단계. 기본단계를 찾는다 (배열원소의 개수를 0개 또는 1개로 한다)

                2단계. 재귀함수를 호출 할 때마다 호출 대상이 되는 배열의 크기가 점점 감소해야 한다.

 

 

퀵 정렬

- 정렬알고리즘, 선택정렬보다 빠르고 실제로 자주 사용된다.

- 분할 정복 전략을 사용한다.

- 배열에서 원소하나를 골라 그 원소를 기준 원소로 정한다.

-순서 1. 모든 원소를 기준 원소보다 작은 원소와 큰 원소로 분류 (분할)

 순서 2. 두개의 하위 배열에 재귀적으로 퀵 정렬을 호출한다.

- 퀵 정렬의 성능은 기준원소에 크게 의존한다

• 항상 첫번째 원소 선택 -> O(n**2)시간, 최악의 시나리고
• 절반으로 나누어 중간 값 선택 -> O(nlogn)시간, 최선의 경우 

아직 정확하게 이해가 안되는데 간단한 문제가 있다면 찾아서 풀어봐야 할 거 같다.