셸 정렬, 퀵 정렬

셸 정렬

셸 정렬은 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행한다.

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]}')