퀵 정렬
- 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방식
- 병합정렬처럼 분할 정복법 사용
- 피봇(pivot)을 요소로 선택, 피봇보다 작은 요소는 피봇의 왼쪽, 큰 요소는 오른쪽으로 이동
- 피봇을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하면 완료
1. 피봇 = 인덱스(처음 + 마지막)/2
왼쪽 : L 오른쪽 : R 피봇 : P
L 은 L >= P 값을 찾게되고 R은 R < P 값을 찾는다
2. 탐색을 하면서 같은 자리의 인덱스에서 만나기전에 두 값을 찾으면 L과 R을 SWAP 해준다
3. L과 R중 하나만 값을 찾고 L과 R이 만날경우 만난 값과 피봇 값을 SWAP 해준다
4. SWAP된 값을 제외한 나머지 부분을 다시 1~4 과정을 반복한다
5. 피벗을 기준으로 왼쪽과 오른쪽 SWAP할 값이 없을경우 각각 따로 정렬을 한다
댓글