[ 개발 공부 ] 퀵 정렬 ( Quick Sort ) 방법

시간 복잡도: O( n log n ), 최악의 경우 O( n^2 )

 

> 퀵 정렬 방법

하나의 배열에서 피벗 하나를 선택한다. ( 보통 맨 처음 인덱스 )

 

선택한 피벗을 기준으로 두 개로 분할하고, 분할된 부분을 퀵 정렬한 다음, 두 개의 정렬된 부분을 합하여 전체가 정렬된 배열이 되게 한다.

 

> 과정
퀵 정렬은 다음의 단계들로 이루어진다.

분할(Divide): 입력 배열을 선택한 피벗을 기준으로 비균등하게 2개의 부분 배열

(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.

정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.

결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

 

 

사실 이미지를 한 번 보면 이해하기 가장 쉽다.

 

구현

 

Pivot을 기준으로 나머지 배열들에서 왼쪽 끝을 low, 오른쪽 끝을 high로 한다.

 

1. low값이 Pivot값보다 클 때까지 오른쪽으로 이동한다.

2. high값이 Pivot값보다 작을 때까지 왼쪽으로 이동한다.

 

3. low와 high가 교차하면 끝내고 high와 pivot값을 스왑한다.

아니라면 low와 high를 스왑하고 low와 high가 교차할 때까지 1~3의 과정을 반복한다.

 

4. Pivot에 왼쪽 부분과 오른쪽 부분을 나눠 각 부분에 1~4의 과정을 부분이 0~1이 될 때까지 반복한다.