Preface
오늘은 퀵 정렬을 공부했다.
일반적인 퀵 정렬에서부터 스택을 사용한 비재귀적 정렬, 특정한 규칙을 적용한 퀵 정렬까지 다양한 방식으로 퀵 정렬을 구현해봤다.
한 번 공부할 때 모든 것을 완벽히 이해할 정도는 아니어도 다시 봤을 때 배웠던 것들을 금방 떠올릴 수 있을 정도로 공부했던 탓인지 3개월 전 업로드했던 스택 관련 코드들은 큰 어려움 없이 사용할 수 있었다.
그러나 배열의 맨 앞, 중간, 맨 끝 원소의 중앙값을 정렬한 후 원소의 수가 9개 미만일 땐 단순 선택 정렬, 10개 이상일 땐 퀵 정렬을 사용하여 결과를 출력하는 코드는 생각할 것도 너무 많고 이것 저것 계산해볼 값들도 다양해서 머리가 너무 복잡했다.
앞으로는 직접 계산하지 않고 종단점을 설정한 후 디버깅을 실행하여 계산 과정을 살펴볼까 하는 생각도 잠시 했지만, 그래도 내 손으로 직접 계산해 보는 것이 기억에 훨씬 오래 남을 것 같아 지금 방식대로 공부를 진행하기로 결정했다.
- 퀵 정렬 : 그룹을 나누는 기준을 설정한 후 모든 그룹이 1명씩 남을 때 까지 나누기를 반복하는 가장 빠른 정렬 알고리즘
→ 서로 떨어져 있는 원소를 교환하므로 안정적이지 않다.
- 피벗(pivot) : 그룹을 나누는 기준
→ 어떤 값으로 선택하느냐에 따라 프로그램의 성능에 영향을 미친다.
- 그룹을 나누는 방법
1) a[pl] >= x가 성립하는 원소를 찾을 때까지 pl을 오른쪽 방향으로 스캔
2) a[pr] >= x가 성립하는 원소를 찾을 때까지 pr을 왼쪽 방향으로 스캔
- 그룹을 나누는 작업이 끝난 후 pl > pr + 1일 경우 피벗과 일치하는 그룹
→ a[pr + 1], ···, a[pl - 1]
- 배열을 두 그룹으로 나누는 코드
from typing import MutableSequence
def partition(a: MutableSequence) -> None:
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)
- 원소 수가 2개 이상인 하위 그룹을 다시 나누는 방법
1) pr이 a[0]보다 오른쪽에 위치하면(left < pr) 왼쪽 그룹을 나눔
2) pl이 a[n - 1]보다 왼쪽에 위치하면(pl < right) 오른쪽 그룹을 나눔
- 퀵 정렬 코드
from typing import MutableSequence
def qsort(a: MutableSequence, left: int, right: int) -> None:
pl = left
pr = right
x = a[(left + right) // 2]
print(f'a[{left}] ~ a[{right}]: ', *a[left:right + 1])
# 나누는 과정 출력
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: # pr이 a[0]보다 오른쪽에 위치하면
qsort(a, left, pr)
if pl < right: # pl이 a[n - 1]보다 왼쪽에 위치하면
qsort(a, pl, right)
def quick_sort(a: MutableSequence) -> None:
n = len(a) - 1
qsort(a, 0, n)
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]}')
- 비재귀적인 퀵 정렬 코드
from stack_sample import Stack
from typing import MutableSequence
def qsort(a: MutableSequence, left: int, right: int) -> None:
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: MutableSequence) -> None:
n = len(a) - 1
qsort(a, 0, n)
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]}')1) range : 나눌 범위에서 맨 앞 원소의 인덱스와 맨 끝 원소의 인덱스를 조합한 튜플 스택
2) 스택의 크기 : right - left + 1
→ 나누는 배열의 원소 수와 같다.
3) 스택에 푸시한 값은 나눠야 할 배열의 맨 앞 원소와 맨 끝 원소의 인덱스
※ 스택 : LIFO
- 배열을 스택에 푸시하는 순서를 정하는 방법
1) 원소 수가 적은 쪽의 그룹을 먼저 푸시
2) 원소 수가 많은 쪽의 그룹을 먼저 푸시
→ 원소 수가 적은 배열일수록 나누는 과정을 빠르게 마칠 수 있다.
∴ 원소 수가 많은 쪽의 그룹을 먼저 푸시하는 것이 효율적이다.
※ 스택에 쌓이는 데이터의 최대 개수는 log n보다 적음
- 전체 배열의 중앙값을 피벗으로 선택하는 것이 가장 이상적이다.
→ 정렬된 배열의 중앙값을 구하려면 계산 시간이 소요된다.
- 적당한 피벗을 선택하는 방법
1) 나누어야 할 배열의 원소 수가 3 이상일 경우, 배열에서 임의의 원소 3개를 꺼내 중앙값을 피벗으로 선택
2) 나누어야 할 배열의 맨 앞, 가운데, 맨 끝 원소를 정렬한 후 가운데 원소와 맨 끝에서 두 번째 원소를 교환한 후 맨 끝에서 두 번째 원소를 피벗으로 선택
→ 나누는 그룹이 한쪽으로 치우지는 것을 피할 수 있다.
→ 스캔할 원소를 3개 줄일 수 있다. (맨 앞의 원소와 맨 끝 + 맨 끝에서 두 번째 원소)
- 특정 규칙을 적용한 퀵 정렬 코드
1) 원소 수가 9개 미만일 경우 단순 삽입 정렬로 전환
2) 피벗 선택은 방법 2를 채택
from typing import MutableSequence
def sort3(a: MutableSequence, idx1: int, idx2: int, idx3: int):
if a[idx2] < a[idx1]:
a[idx2], a[idx1] = a[idx1], a[idx2]
if a[idx3] < a[idx2]:
a[idx3], a[idx2] = a[idx2], a[idx3]
if a[idx2] < a[idx1]:
a[idx2], a[idx1] = a[idx1], a[idx2]
return idx2
def insertion_sort(a: MutableSequence, left: int, right: int) -> None:
for i in range(left + 1, right + 1):
j = i
tmp = a[i]
while j > 0 and a[j - 1] > tmp:
a[j] = a[j - 1]
j -= 1
a[j] = tmp
def qsort(a: MutableSequence, left: int, right: int) -> None:
if right - left < 9:
insertion_sort(a, left, right)
else:
pl = left
pr = right
m = sort3(a, pl, (pl + pr) // 2, pr)
x = a[m]
a[m], a[pr - 1] = a[pr - 1], a[m]
pl += 1
pr -= 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:
qsort(a, left, pr)
if pl < right:
qsort(a, pl, right)
def quick_sort(a: MutableSequence) -> None:
n = len(a) - 1
qsort(a, 0, n)
if __name__ == '__main__':
print('퀵 정렬을 합니다(원소 수가 9 미만이면 단순 삽입 정렬을 합니다).')
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]}')
- sorted( ) 함수를 사용한 정렬 코드
print('sorted( ) 함수를 사용하여 정렬합니다.')
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num
for i in range(num):
x[i] = int(input(f'x[{i}]: '))
# 배열 x를 오름차순으로 정렬
x = sorted(x)
print('오름차순으로 정렬했습니다.')
for i in range(num):
print(f'x[{i}] = {x[i]}')
# 배열 x를 내림차순으로 정렬
x = sorted(x, reverse=True)
print('내림차순으로 정렬했습니다.')
for i in range(num):
print(f'x[{i}] = {x[i]}')
'Algorithm > 자료구조와 함께 배우는 알고리즘(Python)' 카테고리의 다른 글
| 힙 정렬, 도수 정렬 (0) | 2022.01.10 |
|---|---|
| 병합 정렬 (0) | 2022.01.09 |
| 셸 정렬 (0) | 2022.01.06 |
| 단순 선택 정렬, 단순 삽입 정렬 (0) | 2022.01.05 |
| 정렬 알고리즘, 버블 정렬 (0) | 2022.01.02 |
댓글