퀵 정렬(Quick Sort)

대표적인 분할정복 알고리즘으로, 특정한 값(pivot)을 기준으로 큰 값과 작은 값을 나누는 정렬 알고리즘

간단히

① 기준이 되는 값이 5일 때 퀵정렬은 5보다 작은 수는 왼쪽에, 5보다 큰 수는 오른쪽에 정렬한다.
② 5보다 작은 수로 구성된 파티션에서 새로운 기준값에 따라 smaller/bigger 수로 정렬한다.
③ 5보다 큰 수로 구성된 파티션에서 새로운 기준값에 따라 smaller/bigger 수로 정렬한다.

시간 복잡도

• 평균 시간 복잡도 : O(nlogn)
  파티션의 데이터 개수가 1개가 될 때까지 나눈다. 👉 O(n)
  한 번 나눌 때마다 검색(정렬)할 데이터의 개수는 절반이 된다. 👉 O(logn)

• 최악의 시간 복잡도 : O(N^2)
  기준값이 매번 가장 작거나 가장 큰 수인 경우

예제

자세히

• pivot(기준) : 일반적으로 정렬할 데이터의 가운데 숫자로 설정 (정렬할 데이터가 10개라면, 5번째 숫자가 pivot값이 된다)
• s(start) : pivot보다 작으면 건너뜀
• e(end) : pivot보다 크면 건너뜀

while(s의 index < e의 index):
1) 규칙에 맞는 s와 e를 설정(s는 오른쪽으로, e는 왼쪽으로 이동하면서)
2) s와 e를 swap
3) s와 e를 1칸씩 이동
s의 index > e의 index이면 loop 탈출
4) pivot의 왼쪽에 정렬된 수(smaller 부분), pivot의 오른쪽에 정렬된 수(bigger 부분)에 다시 퀵정렬을 수행

구현

1. quick_sort( ) 함수

def quick_sort(data, start, end):
    part = partition(data, start, end)
    if (start < part-1):
        quick_sort(data, start, part-1)
    if (part < end):
        quick_sort(data, part, end)

data : 정렬할 숫자가 들어있는 리스트
start : 시작 인덱스
end : 끝 인덱스
quick_sort( ) 함수 : 파티션의 데이터 개수가 1이 될 때까지 재귀적으로 퀵정렬 함수를 호출한다.

2. partition( ) 함수

def partition(data, start, end):
    pivot = data[(start + end) // 2]
    while (start <= end):
        while (data[start] < pivot):
            start += 1
        while (data[end] > pivot):
            end -= 1
        if (start <= end):
            data[start], data[end] = data[end], data[start]
            start += 1
            end -= 1
    return start

pivot = data[(start + end) // 2]

data의 가운데 값을 pivot으로 설정한다.

while (start <= end):
    while (data[start] < pivot):
        start += 1
    while (data[end] > pivot):
        end -= 1

start의 index가 end의 index보다 작을 때
start는 오른쪽으로 한 칸씩 이동하면서 pivot보다 큰 값을 찾고,
end는 왼쪽으로 한 칸씩 이동하면서 pivot보다 작은 값을 찾는다.

if (start <= end):
    data[start], data[end] = data[end], data[start]
    start += 1
    end -= 1

이전 while문에서 찾은 start의 index가 end의 index보다 작거나 같으면
start와 end를 swap하고, 한 칸씩 이동한다.

전체 코드

github link

def partition(data, start, end):
    pivot = data[(start + end) // 2]
    while (start <= end):
        while (data[start] < pivot):
            start += 1
        while (data[end] > pivot):
            end -= 1
        if (start <= end):
            data[start], data[end] = data[end], data[start]
            start += 1
            end -= 1
    return start

def quick_sort(data, start, end):
    part = partition(data, start, end)
    if (start < part-1):
        quick_sort(data, start, part-1)
    if (part < end):
        quick_sort(data, part, end)

if __name__ == "__main__":
    data = [3, 9, 4, 7, 5, 0, 1, 6, 8, 2]
    quick_sort(data, 0, len(data)-1)
    print("result: ", data)

References
엔지니어대한민국 퀵정렬