퀵 정렬은 피벗(pivot)이라는 기준 데이터를 설정하고 그 기준 데이터보다 큰 데이터와 작은 데이터의 위치를 변경하는 정렬 방식입니다.
퀵 정렬은 데이터 간의 비교만으로 정렬을 수행하는 비교 정렬 중 하나로서 이름에서 알 수 있듯이 정렬이 빠르다는 특징이 있습니다.
퀵 정렬의 방식은 피벗을 설정하고 데이터를 분할하는 방법에 따라 여러 가지로 구분할 수 있습니다.
2. 퀵 정렬의 동작 과정
이제 퀵 정렬의 구체적인 동작 과정을 알아보도록 하겠습니다. "리스트 가장 오른쪽 데이터를 피벗으로 설정한다"와 같은 규칙에 따라
피벗을 선정하겠습니다. 피벗 선정 후 아래와 같은 순서로 데이터를 정렬합니다.
1️⃣ 리스트 좌측에서 우측 방향으로 피벗보다 큰 데이터를 찾고, 리스트 우측에서 좌측 방향으로 피벗보다 작은 데이터를 찾습니다.
2️⃣ 큰 데이터와 작은 데이터의 위치를 서로 교환합니다.
3️⃣ 찾은 데이터의 위치에서부터 다시 조건에 맞는 데이터를 찾고 위치를 서로 변경해 주는 과정을 반복합니다.
퀵 정렬 알고리즘은 왼쪽 파티션과 오른쪽 파티션에 대해 각각 퀵 정렬 알고리즘을 순환적으로 적용합니다.
ADL
quickSort(a[], l, r)
if (r > l) then {
i <- partiotion(a[], l, r);
// i 는 파티션이 끝난 뒤에 사용된 피봇의 인덱스
quickSort(a[], l, i-1);
quickSort(a[], i+1, r);
}
end quickSort;이 퀵 정렬 알고리즘은 주어진 배열 a[]을 두 개의 파티션으로 분할하기 위해 서브 프로그램인 partiotion을 호출합니다.
그런 다음 각 파티션을 정렬하기 위해 자기 자신을 순환적으로 호출합니다.
퀵 정렬 알고리즘의 핵심은 분할 알고리즘이라고 할 수 있습니다.
분할 알고리즘 ADL
partition(a[], l, r)
//가장 오른쪽 원소인 a[r]을 피봇으로 하여 a[]를 분할합니다.
v <- a[r]; // 가장 오른쪽 원소를 피봇으로 정합니다.
i <- l-1; // 왼쪽에서 오른쪽으로 움직이는 포인터입니다.
j <- r; // 오른쪽에서 왼쪽으로 움직이는 포인터입니다.
for( ; ; ) do {
do { i <- i+1; } while ( a[i] < v); // 피봇값보다 작으면 i 값이 증가합니다.
do { j <- j-1; } while ( a[j] > v); // 피봇값보다 크면 i 값이 감소합니다.
if (i >= j) then break;
a[i] 와 a[j] 교환;
}
a[i]와 a[r]를 교환;
return i ;
end patition()
PYTHON
def quickSort(a, l r):
if r > l:
v, i, j = a[r], l-1, r
while True:
i += 1
while a[i] < v:
i += 1
j -= 1
while a[j] > v:
j -= 1
if i >= j:
break
a[i], a[j] = a[j], a[i]
a[r], a[i] = a[i], a[r]
quickSort(a, l, i-1)
quickSort(a, i+1, r)
#퀵 정렬 알고리즘의 성능 향상을 위한 방법
1) 작은 부분 화일
퀵 정렬 수행 중 처리해야할 원소의 개수가 상수 M 보다 작아지게 되면 거의 정렬된 화일이므로, 이것을 작은 부분 화일이라고 부른다.
이렇게 작은 부분 화일의 경우 삽입 정렬 알고리즘을 수행하면 퀵 정렬의 성능을 향상시킬 수 있다.
def quickSort(a, l r):
if r-l <= M:
v, i, j = a[r], l-1, r
while True:
i += 1
while a[i] < v:
i += 1
j -= 1
while a[j] > v:
j -= 1
if i >= j:
break
a[i], a[j] = a[j], a[i]
a[r], a[i] = a[i], a[r]
quickSort(a, l, i-1)
quickSort(a, i+1, r)
2) 중간 값 분할
분할 원소를 선택할 때 왼쪽, 가운데, 오른쪽 원소 중 값이 중간인 원소를 선택하는 방법이다.
왼쪽, 가운데, 오른쪽 원소를 정렬한 후 가장 작은 값을 A[l], 가장 큰 값을 A[r], 중간 값을 A[r-1]에 넣고,
A[l+1], ... A[r-2]에 대해 분할 알고리즘을 수행한다.
이 알고리즘은 최악의 경우가 발생하는 확률을 낮추어준다는 것과 감시키를 사용할 필요가 없다.
또한, 전체 수행 시간을 5% 감소시켜준다.