** divide and conquer(분할 정복) 은 알고 들어가야한다. --> 퀵소트가 사용하는 기법
1.Quick-sort
- random 한 속성을 가진 형태의 input을 정렬하는 데 성능이 매우 좋다.
- pivot 이라는 하나의 element를 기준으로 L(less), E(equal), G(greater)로 나눈다 (분할)
- 나눈후 L 과 G(E U G) 로 다시 recursive하게 sort를 수행한다.
2. Worst Case
- 최악의 경우 pivot을 잡고 분류를 하는 과정에서 L,G를 나누는데 계속 한쪽으로 몰리는 경우 이다
- 이럴경우 n-1번을 나누게 되고 (depth = n), 각 단계에서 약 n, n-1, n-2 ....... 1까지 진행되므로
- running time의 합은 n+(n-1)+ ... +1 이므로 최악의 경우 O(n^2) 이다.
3. Average Case
- 평균분석의 경우 O(n*logn) 이다.
- 최악의 경우는 느리지만 평균분석은 상당히 빠르다.
4. 알고리즘
-partion 별
5. 특징
- partion을 한번 하면 pivot은 자신의 위치를 찾는데 그 자리가 최종 출력 위치이다.
- in-place 로 구현 가능 (추가적으로 사용하는 메모리가 tmp변수 하나 정도로 O(1) 정도
6. 구현
'알고리즘 > 정렬 (sorting)' 카테고리의 다른 글
5. Radix sort (기수 정렬) (0) | 2020.04.19 |
---|---|
4. Heap sort (힙 정렬)--(2) (0) | 2020.04.16 |
4. Heap sort (힙 정렬)--(1) (0) | 2020.04.16 |
3. Merge Sort (합병정렬) -구현 (0) | 2020.04.15 |
1.Insertion sort (삽입정렬) - 구현 (0) | 2020.04.12 |