[Python] 퀵 정렬(Quick Sort)

 

퀵 정렬(Quick Sort)은 병합 정렬(Merge Sort)와 비슷하게 분할정복(Divide and Conqueror)의 방법으로 정렬되는 알고리즘이다. 퀵 정렬은 시간복잡도로는 복불복이다. 최선, 평균의 경우 $O(n\ log\ n)$이지만 최악의 피벗을 선택했을 경우 $O(n^{2})$이다. 공간복잡도는 추가적인 배열을 만들지 않는 In-Place 방식의 경우 추가배열이 만들어지지 않지만 재귀함수 호출로 인해 $O(log\ n)$이다. 추가적인 배열을 선언하는 Non-In-Place 방식은 $O(n)$이다.

 

퀵 정렬(Quick Sort)

 

 

1. pivot을 왼쪽으로 몰거나 오른쪽으로 몰아 하는 방식이 있다.(아래는 왼쪽 이동하는 방법이다.)

2. pivot값을 지정한 후 l ,  r 을 pivot값과 비교해서 작은 값은 왼쪽으로 큰 값은 오른쪽으로 가게 된다.

3. l  >  r 이 되어 더이상 while문이 동작하지 않으면 아까 몰아주었던 pivot값과 s의 값을 바꿔준다. 

4. 왼쪽 작은 배열 - pivot - 오른쪽 큰 배열로 정리되는데 아직 정렬이 완료된 상태는 아니다.

5. 재귀함수로 Quick_sort(왼쪽 작은 배열)과 Quick_sort(오른쪽 큰 배열)을 계속적으로 호출하면서 정렬이 완료된다.

 

 

 

- 코드

 

In-Place, 좌측 Pivot 방식1

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

d = [1, 6, 8, 2, 9, 3, 7, 5, 4]

def quick_sort(d, s=None, e=None):
    if (s, e) == (None, None):
        s, e = 0, len(d)-1
    if s >= e:
        return 
    p = (s+e)//2
    d[s], d[p] = d[p], d[s]
    p = s
    l, r = p+1, e
    while True:
        while l <= r and d[l] <= d[p]:
            l += 1
        while l <= r and d[r] > d[p]:
            r -= 1
        if l > r:
            d[r], d[p] = d[p], d[r]
            break
        else:
            d[l], d[r] = d[r], d[l]
    quick_sort(d, s, r-1)
    quick_sort(d, r+1, e)
    return d

print(quick_sort(d))

 

In-Place, 좌측 Pivot 방식2

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

d = [1, 6, 8, 2, 9, 3, 7, 5, 4]

def quick_sort(d, s=None, e=None):
    if (s, e) == (None, None):
        s, e = 0, len(d)-1

    def qsort(d, s, e):
        if s >= e:
            return 
        p = partition(d, s, e)
        quick_sort(d, s, p-1)
        quick_sort(d, p+1, e)
        return d

    def partition(d, s, e):
        p = (s+e)//2
        d[s], d[p] = d[p], d[s]
        p = s
        l, r = p+1, e
        while True:
            while l <= r and d[l] <= d[p]:
                l += 1
            while l <= r and d[r] > d[p]:
                r -= 1
            if l > r:
                d[r], d[p] = d[p], d[r]
                break
            else:
                d[l], d[r] = d[r], d[l]
        return r
    
    return qsort(d, s, e)

print(quick_sort(d))

 

In-Place, 우측 Pivot 방식1

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

d = [1, 6, 8, 2, 9, 3, 7, 5, 4]

def quick_sort(d, s=None, e=None):
    if (s, e) == (None, None):
        s, e = 0, len(d)-1
    if s >= e:
        return 
    p = (s+e)//2
    d[e], d[p] = d[p], d[e]
    p = e
    swap_idx, i = 0, 0
    while i < e:
        if d[i] < d[p]:
            d[i], d[swap_idx] = d[swap_idx], d[i]
            swap_idx += 1
        i += 1
    d[swap_idx], d[e] = d[e], d[swap_idx]
    quick_sort(d, s, swap_idx-1)
    quick_sort(d, swap_idx+1, e)
    return d

print(quick_sort(d))

 

Non-In-Place 방식

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

d = [1, 6, 8, 2, 9, 3, 7, 5, 4]

def quick_sort(d):
    if len(d) < 2:
        return d
    p = len(d)//2
    S, L = [], []
    for i in range(len(d)):
        if d[i] < d[p]:
            S.append(d[i])
        if d[i] > d[p]:
            L.append(d[i])
    return quick_sort(S) + [d[p]] + quick_sort(L) 

print(quick_sort(d))

 

 

 

 

[Python] 병합 정렬(Merge Sort)

 

[Python] 힙 정렬(Heap Sort)