[알고리즘] Quick Sort 의 개념

1. Quick Sort 코드

 

def swap(a, b):
    return b, a


def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r-1):
        if A[j] <= x:
            i = i + 1
            A[i], A[j] = swap(A[i], A[j])
    A[r], A[i + 1] = swap(A[r], A[i + 1])

    return i+1


def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)

    return A

l = [2, 1, 5, 7, 4, 9, 12, 3]
quicksort(l, 0, 7)
print(l)

 

위의 코드는 Quick Sort를 수행하는 python 코드다.

 

 

 

2. 기본 알고리즘

 

Quick Sort는 기본적으로 배열을 오름차순 혹은 내림차순으로 정렬하는 알고리즘이다.

코드를 보면 대충 알 수 있겠지만, Divide-and-conquer 알고리즘을 활용하여 구현한다.

 

Quick Sort 알고리즘의 원리는 다음과 같다.

 

  step 1) 배열의 한 원소를 잡아 pivot으로 정한다.

  step 2) 해당 pivot을 기준으로, pivot보다 작은 원소들은 왼쪽에, pivot보다 큰 원소들은 오른쪽에 놓는다.

  step 3) pivot을 기준으로 양쪽의 sub-array를 대상으로 다시 step 1) 부터 반복한다.

 

pivot을 기준으로 쪼개진 2개의 sub-arrays

 

간단하게 예시를 통해 알아보자.

아래와 같은 배열이 있다고 가정하자. pivot은 해당 배열에서 가장 마지막 원소로 정한다.

 

 

pivot인 5를 기준으로 왼쪽으로는 5보다 작은 원소들,  오른쪽으로는 5보다 큰 원소들을 채워준다.

 

 

이제 양쪽의 배열에 대하여 다시 pivot을 잡아주고 계속해서 반복한다.

 

 

 

다시 코드로 돌아가보자.

 

def partition(A, p, r):		# A 배열의 시작 index는 p, 마지막 index는 r
    x = A[r]
    i = p - 1
    for j in range(p, r-1):
        if A[j] <= x:
            i = i + 1
            A[i], A[j] = swap(A[i], A[j])
    A[r], A[i + 1] = swap(A[r], A[i + 1])

    return i+1

 

Quick Sort의 핵심은 바로 pivot을 중심으로 두개의 sub-array로 쪼개는 partition 함수이다.

 

특히 for문을 거치고 나면 pivot값을 중심으로 작은 원소는 왼쪽으로, 큰 원소는 오른쪽으로 나누어진다. 해당 과정은 Quick Sort 이외에도 많이 쓰이므로 익숙해지는게 좋다.

 

def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)

    return A

 

quicksort 함수 내에서는 partition 함수를 호출해 pivot을 기준으로 두개의 sub-array로 나눠주고, 양쪽의 sub-array를 각각 다시 quicksort 함수에 넣어줌으로써 수행된다.

 

 

 

3. 시간복잡도

 

Quick Sort의 시간복잡도의 경우, n log(2) n 이다.

 

worst case의 경우, 한번에 하나의 원소만이 정렬되므로 시각복잡도는 O(n^2)이 된다.

 

위 내용은 공부하며 작성한 것으로, 오류가 있을 수 있습니다.