[자료구조 및 알고리즘] (6) Quick sort (퀵 정렬)의 소개

1. Quick sort의 소개 quick sort는 정렬 기법 중 하나이다.

실제로 많이 사용되는데, 특징은 다음과 같다. in place implementation; 새로운 memory allocation이 필요가 없다. on average, works with O(nlogn), 머지소트와 비슷하지만 constant가 작다. randomization을 활용한다. Quicksort(A, n) if n==1 return p = choosePivot(A,n) partition(A, left, right) //currently unimplemented Quicksort(left half) Quicksort(right half) 2.

Quick sort의 방법 1. 랜덤하게 pivot을 하나 고른다. 2.

그 pivot보다 작은 숫자는 왼쪽으로, 큰 숫자는 오른쪽으로 옮긴다. 3. 왼쪽과 오른쪽에 대해서 recursive하게 정렬한다.

그렇다면 어떻게 pivot을 기준으로 왼/오로 나눌까...