셸 정렬
셸 정렬은 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행한다.
h=4일때 4칸씩 떨어진 원소를 비교하여 바꿔준다.
8 1 4 2 7 6 3 5
h = 2일때, 2칸씩 떨어진 원소를 그룹으로 나눠 정렬한다.
7 1 3 2 8 6 4 5
3 1 4 2 7 5 8 6
두 그룹으로 나누어 두번 정렬 한다
h=1 로 하여 전체 그룹으로 한번 정렬을 수행한다.
1 2 3 4 5 6 7 8
이렇게 하여 총 7번 정렬을 하게 되고, 4그룹, 2그룹, 1그룹씩 나누어 정렬을 수행한다.
def shell_sort(a: MutableSequence) -> None:
"""셸 정렬"""
n = len(a)
h = n // 2
while h > 0:
for i in range(h, n):
j = i - h
tmp = a[i]
while j >= 0 and a[j] > tmp:
a[j + h] = a[j]
j -= h
a[j + h] = tmp
h //= 2
h의 초기값을 n을 2로 나눈 몫(int형)으로 정한다. while 문을 반복할 때 마다 2로 나눈다.
만약 n이 8이면 4->2->1, 7이면 3-> 1 로 한다.
from typing import MutableSequence
def shell_sort(a: MutableSequence) -> None:
"""셸 정렬(h * 3 + 1의 수열 사용)"""
n = len(a)
h = 1
while h < n // 9:
h = h * 3 + 1
while h > 0:
print(f'h = {h}일 때:') # 현재 h 값을 출력
for i in range(h, n):
j = i - h
tmp = a[i]
while j >= 0 and a[j] > tmp:
a[j + h] = a[j]
j -= h
a[j + h] = tmp
print(a) # 현재 단계에서 배열의 상태 출력
h //= 3 #3으로 나누기 계속해서 결국은 1 출력함
h값이 서로 배수가 되지 않도록 하면 원소가 충분히 뒤섞인다. 3배한값에 1을 더한다. 하지만 h의 초기값이 지나치게 크면 효과가 없기 때문에 9로 나누었을 때의 몫을 넘지 않도록 해야한다.
퀵 정렬
pl x pr
5 | 7 | 1 | 4 | 6 | 2 | 3 | 9 | 8 |
pl에서 x 방향으로, pr에서 x 방향으로 a[pl] >= x, a[pr] <= x 가 성립하는 원소를 찾을때까지 스캔함
5 | 7 | 1 | 4 | 6 | 2 | 3 | 9 | 8 |
5 | 3 | 1 | 4 | 2 | 6 | 7 | 9 | 8 |
pr pl
2 뒤에 있는 원소들은 피벗이하그룹(a[0],, a[pl-1]), 6이상의 원소는 피벗 이상 그룹(a[pr+1],,,a[n-1])으로 나뉜다.
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]
print(f'스왑: a[{pl}]과(와) a[{pr}]를 스왑합니다.') # 스왑하는 부분 출력
print(*a) # 스왑 후의 배열 상태를 출력
pl += 1
pr -= 1
가운데 원소가 pl보다 크면 오른쪽으로 한칸씩, 가운데 원소가 pr보다 작으면 왼쪽으로 한칸씩 이동하고, 왼쪽원소가 오른쪽 원소보다 작으면 배열을 바꾼다.
퀵 정렬 만들기
a) left=0, right =8
b) left=0,right=4
c) left=5, right =8
def qsort(a: MutableSequence, left: int, right: int) -> None:
"""a[left] ~ a[right]를 퀵 정렬(배열을 나누는 과정 출력)"""
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: qsort(a, left, pr)
if pl < right: qsort(a, pl, right)
비재귀적인 퀵 정렬
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] # 피벗(중앙 요소)
print(f"\n피벗 선택: {x}, 범위: {left} ~ {right}")
while pl <= pr:
while a[pl] < x: pl += 1
while a[pr] > x: pr -= 1
if pl <= pr:
print(f"교환 전: {a}, 교환 위치: {pl}과 {pr}")
a[pl], a[pr] = a[pr], a[pl]
print(f"교환 후: {a}")
pl += 1
pr -= 1
if left < pr: range.push((left, pr)) #튜플(0,4)푸시/(5,6) push
if pl < right: range.push((pl, right)) #튜플(5,8) push/(7,8)push
def quick_sort(a: MutableSequence) -> None:
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]}')
(0,8) -> (0,4) (5,8) -> (5,6)(7,8)
-> (0,2)(3,4)
-> (0,1)(2)
피벗 선택하기
빠른 정렬을 위해서는 중앙값을 피벗으로 하는것이 이상적이다. 그래야 배열이 한쪽으로 치우치지 않고 절반 크기로 나누어진다.
나누어야 할 배열의 맨 앞원소 a[0], 가운데 원소, 맨 끝 원소를 정렬한뒤 /가운데 원소와 맨끝 두번째 원소를 교환한다.
8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
0 | 7 | 6 | 5 | 1 | 3 | 2 | 4 | 8 |
pl(여기부터 스캔) pr(여기부터 스캔)
a[1]부터 a[6]까지 스캔 과정을 거친다.
왼쪽 커서 pl의 위치 left+1, 오른쪽 커서 위치는 right +2가 된다.
퀵 정렬의 시간 복잡도
원소수가 9개 미만인 경우 단순 삽입 정렬로 전환하고, 피벗 선택은 방법2를 채택한다.
from typing import MutableSequence
def sort3(a: MutableSequence, idx1: int, idx2: int, idx3: int):
"""a[idx1], a[idx2], a[idx3]을 오름차순으로 정렬하고 가운데 값의 인덱스를 반환"""
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:
"""a[left] ~ a[right]를 단순 삽입 정렬"""
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:
"""a[left] ~ a[right]를 퀵 정렬"""
if right - left < 9: # 원소 수가 9개 미만이면 단순 삽입 정렬을 호출
insertion_sort(a, left, right)
else: # 원소 수가 9개 이상이면 퀵 정렬을 수행
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:
"""퀵 정렬"""
qsort(a, 0, len(a) - 1)
if __name__ == '__main__':
print('퀵 정렬을 합니다(원소 수가 9개 미만이면 단순 삽입 정렬).')
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num # 원소 수가 num인 배열을 생성
for i in range(num):
x[i] = int(input(f'x[{i}]: '))
quick_sort(x) # 배열 x를 퀵 정렬
print('오름차순으로 정렬했습니다.')
for i in range(num):
print(f'x[{i}] = {x[i]}')
'자료구조' 카테고리의 다른 글
문자열 검색 (0) | 2024.03.19 |
---|---|
병합 정렬, 힙 정렬, 도수 정렬 (0) | 2024.03.19 |
버블정렬, 단순 선택 정렬, 단순 삽입 정렬 (0) | 2024.03.17 |
하노이의 탑, 8퀸문제(재귀함수 응용) (1) | 2024.03.15 |
재귀 알고리즘 (0) | 2024.03.09 |