-
정의
퀵 정렬(suick sort)은 가장 빠른 정렬 알고리즘으로 알려져 있으며 널리 사용된다.
배열 안의 한 원소(요소)를 선택하는 데, 이 원소를 pivot이라고 한다. pivot을 기준으로 pivot보다 작은 원소들은 왼쪽 그룹으로 큰 원소들은 오른쪽 그룹으로 옮긴다. 다시 각 그룹에서 pivot을 선택하여 나누기를 반복하고 모든 그룹이 1명씩 남으면 정렬이 완료된다.
example 1. 배열을 두 그룹으로 나누기
5 7 1 4 6 2 3 9 8 위의 배열에서 6을 pivot으로 선택하여 그룹을 나눈다. pivot을 x, 왼쪽 끝 원소의 인덱스를 pl, 오른쪽을 pr이라고 하겠다.
그룹을 나누려면 pivot 이하인 원소를 배열 왼쪽(맨 앞쪽)으로, 피벗 이상인 원소를 배열 오른쪽(맨 뒤쪽)으로 이동시켜야 한다.
- a[pl] >= x 가 성립하는 원소를 찾을 때까지 pl을 오른쪽 방향으로 스캔한다.
- a[pr] <= x 가 성립하는 원소를 찾을 때까지 pr을 왼쪽 방향으로 스캔한다.
이 과정을 거치면 pl은 x보다 큰 a[1], pr은 x보다 작은 a[6]에서 멈추고, pl과 pr 서로의 값을 교환한다. 다시 스캔을 진행한다.
pl과 pr이 교차하면 이로써 그룹을 나누는 과정이 끝나고, 배열은 다음과 같은 두 그룹으로 나뉜다.
- pivot 이하의 그룹 : a[0], ... a[pl - 1]
- pivot 이상의 그룹 : a[pr + 1], ... a[n - 1]
배열을 두 그룹으로 나누는 소스코드.
<code>
더보기def partition(a): n = len(a) pl = 0 pr = n - 1 x = a[n // 2] while pl <= pr: while a[pl] < x: pl += 1 while a[pr] > x: pr -= 1 if pl <= pr: a[pl], a[pr] = a[pr], a[pl] pl += 1 pr -= 1 print(f'피벗은 {x}입니다.') print('피벗 이하인 그룹입니다.') print(*a[0 : pl]) if pl > pr + 1: print('피벗과 일치하는 그룹입니다.') print(*a[pr+1 : pl]) print('피벗 이상인 그룹입니다.') print(*a[pr + 1 : n]) if __name__ == '__main__': print('배열을 나눕니다.') num = int(input('원소 수를 입력하세요 : ')) x = [None] * num for i in range(num): x[i] = int(input(f'x[{i}] : ')) partition(x)- 이 프로그램에선 배열 가운데에 있는 원소를 pivot으로 정했다. 어떤 값을 pivot으로 정하느냐에 따라 배열을 나누는 것과 정렬하는 성능에 영향을 미친다.
2. 퀵 정렬 만들기
배열을 두 그룹으로 나누는 과정을 조금 더 발전시키면 퀵 정렬 알고리즘이 된다.
위의 그림을 보면 원소가 9개인 배열 a를 나누면 그림 a처럼 a[0]~a[4]인 그룹과 a[5]~a[8]인 그룹으로 나뉜다. 그리고 그림 b, c처럼 나누어진 두 그룹에 같은 과정을 적용하여 다시 나눈다.
원소 수가 1개인 그룹은 더 이상 나눌 필요가 없으므로 원소 수가 2개 이상인 그룹만 다음과 같이 반복해서 나눈다.
- pr가 a[0]보다 오른쪽에 위치하면 (left < pr) 왼쪽 그룹을 나눈다.
- pl이 a[8]보다 왼쪽에 위치하면 (pl < right) 오른쪽 그룹을 나눈다.
퀵 정렬은 퀸 문제와 같은 분할 정복 알고리즘이므로 재귀 호출을 사용하여 구현할 수 있다.
<code>
더보기def qsort(a, left, right): '''a[left] ~ a[right]를 정렬''' pl = left pr = right x = a[(left + right) // 2] # pivot while pl <= pr: while a[pl] < x: pl += 1 while a[pr] > x: pr -= 1 if pl <= pr: a[pl], a[pr] = a[pr], a[pl] pl += 1 pr -= 1 #재귀 호출 추가 if left < pr: qsort(a, left, pr) if pl < right: qsort(a, pl, right) def quick_sort(a): '''퀵 정렬''' qsort(a, 0, len(a) - 1) if __name__ == '__main__': print('퀵 정렬을 수행합니다.') num = int(input('원소 수를 입력하세요 : ')) x = [None] * num for i in range(num): x[i] = int(input(f'x[{i}]: ')) quick_sort(x) print('오름차순으로 정렬했습니다.') for i in range(num): print(f'x[{i}] = {x[i]}')비재귀적인 퀵 정렬은 재귀 함수 recur()를 비재귀적으로 구현하는 방법과 같이 만들 수 있다.
<code>
더보기from stack import Stack def qsort(a, left, right): '''a[left] ~ a[right]를 정렬''' range = Stack(right - left + 1) # 스택 생성 range.push((left, right)) while not range.is_empty(): pl, pr = left, right = range.pop() # 왼쪽, 오른쪽 커서를 꺼냄 x = a[(left + right) // 2] while pl <= pr: while a[pl] < x: pl += 1 while a[pr] > x: pr -= 1 if pl <= pr: a[pl], a[pr] = a[pr], a[pl] pl += 1 pr -= 1 if left < pr: range.push((left, pr)) if pl < right: range.push((pl, right)) def quick_sort(a): '''퀵 정렬''' qsort(a, 0, len(a) - 1) if __name__ == '__main__': print('퀵 정렬을 수행합니다.') num = int(input('원소 수를 입력하세요 : ')) x = [None] * num for i in range(num): x[i] = int(input(f'x[{i}]: ')) quick_sort(x) print('오름차순으로 정렬했습니다.') for i in range(num): print(f'x[{i}] = {x[i]}')
pivot 선택하기
pivot 선택 방법은 퀵 정렬의 실행 효율에 큰 영향을 미친다. 예를 들어 아래 배열의 맨 앞 원소(8)를 pivot으로 선택한다.
8 7 6 5 4 3 2 1 0 이 배열은 pivot(8)만 있는 그룹과 나머지 원소 그룹으로 나누어야 한다. 하나의 원소와 그 외 나머지 원소로 나누는 것은 한쪽으로 완전히 치우친 분할을 반복하므로 빠른 정렬 속도를 기대할 수 없다.
빠른 정렬을 원한다면 배열을 정렬한 뒤 가운데에 위치하는 값, 즉 전체에서 중앙값을 pivot으로 하는 것이 이상적이다. 그러면 배열이 한쪽으로 치우치지 않고 절반 크기로 나누어진다. 하지만 정렬된 배열의 중앙값을 구하려면 그에 대한 처리가 필요하고, 처리를 위해 많은 계산 시간이 걸린다. 결국 pivot을 선택하는 의미가 없어진다.
최악의 경우를 피하는 방법 : 나누어야 할 배열의 맨 앞 원소, 가운데 원소, 맨 끝 원소를 정렬한 뒤 가운데 원소와 맨 끝에서 두 번째 원소를 교환한다. 맨 끝에서 두 번째 원솟값 a[right - 1]이 피벗으로 선택되었고, 그 동시에 나눌 대상을 a[left + 1] ~ a[right - 2]로 좁힌다.
퀵 정렬의 시간 복잡도
퀵 정렬은 배열은 조금씩 나누어 보다 작은 문제를 푸는 과정을 반복하므로 시간 복잡도는 O(n log n)이다. 그런데 정렬하는 배열의 초깃값이나 피벗을 선택하는 방법에 따라 실행시간 복잡도가 증가하는 경우도 있다. 예를 들어 매번 1개의 원소와 나머지 원소로 나누어진다면 n번의 분할이 필요하다. 이러한 최악의 경우 O(n^2)이 된다. 그래서 원소 수가 9개 미만인 경우 단순 삽입 정렬로 전환한다.