퀵 정렬 (Quick Sort)

퀵 정렬 (Quick Sort)

퀵 정렬 (Quick Sort)은 '찰스 앤터니 리차드 호어 (Charles Antony Richard Hoare)가 

개발한 정렬 알고리즘이다.

다른 원소와의 비교만으로 정렬하는 "비교 정렬"에 속하며, 

분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 갖는다.

비교 정렬의 시간복잡도 하한선 : O(nlogn)  / 퀵 정렬의 평균 시간복잡도 O(nlogn)

(이름 자체에서도 빠르다는 것을 알려주고 있다...)

 

 

퀵 정렬 (Quick Sort) 알고리즘의 동작 원리

<Main> 기준점(pivot)을 설정해 해당 기준으로 분할

 

i) 리스트 중에서 한 원소를 선택한다. 이렇게 고른 원소를 피벗(Pivot)이라고 한다.

(일반적으로는 pivot을 리스트의 가장 앞의 원소 혹은 가장 뒤의 원소로 설정한다)

ii) Pivot을 기준으로 Pivot보다 '작은' 원소들은 Pivot의 앞(왼쪽)으로, 

'큰' 원소들은 Pivot의 뒤(오른쪽)으로 이동시킨다.

iii) Pivot을 제외하고, Pivot의 왼쪽 부분과 오른쪽 부분으로 리스트를 "분할"한다.

iv) 분할된 두 리스트에 각각 i~iii)의 과정을 반복한다.

v) 리스트가 더이상 분할이 되지 않을 때 종료한다. 

 

퀵 정렬 (Quick Sort) 알고리즘의 실제 코드 원리 (예시 포함)

i) pivot을 리스트의 맨 앞 원소 또는 맨 뒤 원소로 설정

(예시에서는 맨 앞 원소로 pivot 설정)

 

ii) pivot보다 큰 값이 나올 때까지 low 이동 / pivot보다 작은 값이 나올 때까지 high 이동

  이 때, low는 low의 왼쪽까지는 pivot보다 작은 값이,

  high는 high의 오른쪽까지는 pivot보다 큰 값으로 정렬되었다는 의미이다.

  (low는 pivot을 제외한 리스트의 가장 왼쪽(left)에서, high는 가장 오른쪽(right)에서 출발)

 

(하늘색 부분은 현재 정렬이 된 부분)

 

 

iii) low와 high가 둘 다 멈추었다면 low와 high 교환 / ii)의 과정 반복

 

 

iv) low와 high가 엇갈려서 지났다면 수행을 멈추고, pivot과 high위치의 원소 교환

 

v) pivot을 기준으로 분할된 두 리스트에 i) ~ iv) 과정 반복

 

 

 

 

퀵 정렬 (Quick Sort)의 장단점

 

<장점> 

  1. 속도가 빠르다 (같은 시간 복잡도인 O(nlogn)을 갖는 다른 정렬 알고리즘과 비교해도 빠르다)

  2. 추가 메모리 공간을 필요로 하지 않는다.

 

<단점>

  1. pivot 설정에 따라 오히려 정렬된 리스트에서의 수행 시간이 더 많이 걸릴 수 있다. 

   (퀵 정렬의 불균형 분할에 의해) 

 

 

 

퀵 정렬 (Quick Sort) 알고리즘 코드 (C 언어)