불안정 정렬 (Unstable Sort) 에 속하며 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속함

분할 정복 알고리즘 중 하나이고, 이름과 같이 매우 빠른 수행 속도를 자랑하는 정렬 방법이다.

합병 정렬 (MergetSort)와 다르게 퀵 정렬은 리스트를 비균등하게 분할한다.

• 분할 (Divide) : 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
• 정복 (Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면, 재귀 호출을 이용하여 다시 분할을 적용한다.
• 결합 (Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.

재귀 호출이 한번 진행될 때 마다 최소 하나의 원소(피벗)은 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장 할 수 있다.

예시

리스트에 5,3,8,4,9,1,6,2,7이 저장되어 있다고 가정할 때 오름차순 정렬

피벗을 입력된 리스트중 0번 인덱스인 5로 선택 (다른 임의의 값이어도 상관 없다.)

2개의 인덱스 변수 (Low, High)를 이용해서 리스트를 두 개의 부분 리스트로 나눈다.

1회전 (피벗이 5인 경우)

Low는 왼쪽에서 오른쪽으로 탐색하다가 피벗보다 큰 데이터 (8)을 찾으면 멈춘다.

High는 오른쪽에서 왼쪽으로 탐색하다가 피벗보다 작은 데이터 (2)를 찾으면 멈춘다.

Low와 High가 가리키는 두 데이터를 서로 교환한다.

이 과정을 Low와 High가 엇갈릴 때 까지 반복 한다.

2회전 (피벗이 1인 경우, 1회전의 왼쪽 부분리스트의 첫 번째 데이터)

위와 같은 방법으로 진행

3회전 (피벗이 9인 경우, 1회전 오른쪽 부분리스트의 첫 번째 데이터)

위와 같은 방법으로 진행