퀵 정렬(Quick sort)개념 및 구현 방법(python)
1. 정의
퀵 정렬은 이름에서 알 수 있듯이, 가장 빠른 알고리즘 중 하나로,
임의로 pivot(중심)을 지정하여, pivot 값보다 작은 값은 왼쪽, 큰 값들은 오른쪽에 위치하도록 만드는 정렬 기법입니다
*pivot이란?
어떠한 대상의 중심 축
2. 동작 방식
a = [5, 7, 1, 4, 6, 2, 3, 9, 8]
I. 배열의 pivot을 지정합니다. 가장 가운데인 6을 pivot으로 지정합니다
II. pivot을 기준으로 배열의 처음을 가리키는 왼쪽 포인터(pl) 배열의 마지막을 가리키는 오른쪽 포인터(pr)을 설정합니다
III. 왼쪽 포인터가 가리키는 값이 pivot보다 커질때까지 오른쪽으로 이동합니다. (위 배열에서 7을 가리키면 종료)
IV. 오른쪽 포인터가 가리키는 값이 pivot보다 작아질때까지 왼쪽으로 이동합니다. (위 배열에서 3을 가리키면 종료)
V. 현재 각 포인터가 가리키는 값을 swap하고, 위 과정을 반복합니다.
VI. 포인터가 교차하는 시점(pl이 pr의 오른쪽을 가리킴)에 배열은 다음과 같이 두 그룹으로 나눕니다
- pivot 이하인 그룹
- pivot 이상인 그룹
이후, 각각의 그룹에 대해서 pivot을 지정한 뒤, I ~ VI 과정을 반복합니다(재귀적으로 호출)
*재귀란?
자기자신을 호출하는 방식
자세한 설명은 아래링크
3. 구현하기
def quick_sort(a: MutableSequence, left : int, right : int ) -> None:
pl = left
pr = right
pivot = a[(left + right) // 2]
while pl <= pr:
while a[pl] < pivot : pl +=1
while a[pr] > pivot : pr -=1
if pl <= pr:
a[pl], a[pr] = a[pr], a[pl]
pl +=1
pr -=1
if left < pr : quick_sort(a, left, pr)
if pl < right: quick_sort(a, pl, right)
I. quick sort를 실행 할 배열, 왼쪽 포인터 위치, 오른쪽 포인터 위치를 입력 받습니다.
II. pivot(중심축)을 설정합니다.
III. pl <= pr이 될때까지 반복합니다
IV. a[pl]이 pivot보다 크거나 같을때까지 pl 값을 1씩 올립니다 / a[pr]이 pivot보다 작거나 같을때까지 pr 값을 1씩 올립니다
V. pl <= pr 이면, a[pl]과 a[pr]을 변경합니다
pivot 왼쪽에 있는 값들은 pivot보다 작아야합니다. 그렇기 때문에 pivot보다 큰 값을 왼쪽에서 찾습니다.
pivot 오른쪽에 있는 값들은 pivot보다 커야하기 때문에, pivot보다 작은 값을 찾습니다.
두 값을 교환하면, 왼쪽에는 pivot보다 작은 값이, 오른쪽에는 pivot보다 큰 값이 위치합니다(올바르게 정렬)
VI. 만약, pr이 아직 left 값보다 큰 상태(pivot 왼쪽을 모두 탐색하지 않았을 경우)일 경우 quick_sort를 재귀적으로 호출합니다
VII. 아래 과정은 동일하게 진행됩니다
4. 시간 복잡도
quick sort는 원소의 개수가 많을 때는, 느린 알고리즘이며 원소가 많고 어느정도 정렬되어 있을 때, 효율이 좋은 알고리즘입니다.
보통 데이터를 저장할 때, 어느정도 '정렬된 상태'로 데이터를 저장하기 때문에, quick sort를 사용하면 효율이 좋습니다
기본 시간 복잡도는 O(logn n)이며
최악의 경우 O(n^2)입니다
pivot을 가장 큰 값으로 설정한다면, 배열 내 모든 원소 n-1개를 모두 탐색해야하기에, pivot을 연속적으로 잘못 설정할 경우 O(n^2)이 됩니다