정렬 알고리즘_셸 정렬, 퀵 정렬

 

  셸 정렬  

 

단순 삽입 정렬의 장점 + 단점 보완한 더 빠른 정렬 알고리즘

 

단순 삽입 정렬

장점 : 이미 정렬을 마쳤거나 끝나가는 상태에서 매우 빠른 속도

단점 : 삽입할 위치가 멀면 이동 횟수가 많아짐

 

정렬횟수는 증가하나, 전체적으로 원소의 이동 횟수가 줄어 효율적

 

서로 h 만큼 떨어진 원소를 꺼내 그룹으로 만들고 그룹별로 정렬 = h-정렬

ex) 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 값의 선택 : h 값이 서로 배수가 되지 않아야 원소가 충분히 뒤섞여 효율적인 정렬 가능 

 

  퀵 정렬  

피벗(pivot)을 기준으로 그룹을 나눠 피벗 이상/이하 원소를 찾아 교환하는 과정을 통해 정렬

가장 빠른 정렬 알고리즘으로 알려져있음

시간 복잡도 O(n log n) -> 원소의 수가 적은 경우에는 다른 알고리즘이 빠를 수 도 있음

 

def qsort(a: MutableSequence, left: int, right: int) -> None:
    pl = left       # 왼쪽 커서
    pr = right      # 오른쪽 커서
    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: qsort(a, left, pr)
        if pl < right: qsort(a, pl, right)
 
def quick_sort(a: MutableSequence) -> None:
    qsort(a, 0, len(a) - 1)