[알고리즘] 퀵정렬(Quick Sort)

퀵 정렬

1. 분할(divide) :

먼저 피벗(pivot)을 선택한다. 

편의상 리스트이 첫 번째 항목을 사용

피벗보다 작은 항목들은 모두 피벗의 왼쪽으로 옮기고

피벗보다 큰 항목들은 모두 피벗의 오른쪽으로 옮긴다

 

2.정복(Conquer) : 

분할이 끝나면 피벗은 최종 위치에 있지만

왼쪽과 오른쪽 부분 리스트는 아직 정렬 미완성

분할 정복 전략을 다시 사용한다

만약 리스트의 크기가 1이면 이미 정복된 것!

 

3. 결합(Combine, merge) : 

병합단계는 필요 없는 데 분할 할 때마다 

피벗 중심으로 부분리스트로 정렬되기 때문이다.

분할과 정복이 모두 끝나면 그 자체가 이미 정렬 완료된 상태