퀵 정렬 (Quick Sort)

퀵 정렬 알고리즘의 기본 개념

• 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
• 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 가진 정렬 방법이다.
  • 병합 정렬과 다르게 퀵 정렬은 리스트를 비균등하게 분할한다.
• 분할 정복 방법
  • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
  • 분할 정복 방법은 대게 순환 호출을 이용하여 구현한다.
• 알고리즘의 과정
  • 리스트 안에 있는 한 원소를 선택한다. 이렇게 고른 원소를 피벗(pivot)이라고 한다.
  • 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다.
  • 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
    • 분할된 부분 리스트에 대하여 재귀적 호출을 이용하여 정렬을 반복한다.
    • 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
  • 부분 리스트들이 더이상 분할이 불가능할 때까지 반복한다.
    • 리스트의 크기가 0이나 1이 될 때까지 반복한다.

파이썬으로 코드 구현

 

코드 구현

def quicksort(data):
    if len(data) <= 1:
        return data
    
    pivot = data[len(data) // 2]   # 피벗값을 중앙값으로 잡기
    
    left = []   # 피벗값보다 작은 데이터는 피벗의 왼쪽으로 정렬
    for num in data:
        if num < pivot:
            left.append(num)
    
    mid = []    # 피벗과 같은값이 있으면 mid 리스트로 추가
    for num in data:
        if num == pivot:
            mid.append(num)

    right =[]   # 피벗값보다 큰 데이터는 피벗의 오른쪽으로 정렬
    for num in data:
        if num > pivot:
            right.append(num)

    return quicksort(left) + mid + quicksort(right)   # 이 과정을 재귀 호출로 반복

 

알고리즘 테스트 1

data = [1, 9, 5, 8, 4, 6, 5, 3, 2, 7, 1, 9, 10]
print(quicksort(data))

 

결과

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

 

알고리즘 테스트 2

 

아래의 네가지 데이터를 넣고 테스트도 진행해 보았다.

1. 정렬이 끝난 배열
2. 역순으로 정렬된 배열
3. 원소가 전부 같은 배열
4. 랜덤으로 구성된 배열

import time

def quicksort(data):
    if len(data) <= 1:
        return data
    
    pivot = data[len(data) // 2]
    
    left = []
    for num in data:
        if num < pivot:
            left.append(num)
    
    mid = []
    for num in data:
        if num == pivot:
            mid.append(num)

    right =[]
    for num in data:
        if num > pivot:
            right.append(num)

    return quicksort(left) + mid + quicksort(right)
    
test1 = [1, 2, 3, 4, 5, 6, 7]
test2 = [7, 6, 5, 4, 3, 2, 1]
test3 = [1, 1, 1, 1, 1, 1, 1, 1]
test4 = [23, 15, 38, 94, 62, 123, 243, 234, 112]

start_time1 = time.time()
mergesort(test1)
end_time1 = time.time()
total_time1 = (end_time1 - start_time1) * 1000

start_time2 = time.time()
mergesort(test2)
end_time2 = time.time()
total_time2 = (end_time2 - start_time2) * 1000

start_time3 = time.time()
mergesort(test3)
end_time3 = time.time()
total_time3 = (end_time3 - start_time3) * 1000

start_time4 = time.time()
mergesort(test4)
end_time4 = time.time()
total_time4 = (end_time4 - start_time4) * 1000

print(f'{total_time1:.4f}ms')
print(f'{total_time2:.4f}ms')
print(f'{total_time3:.4f}ms')
print(f'{total_time4:.4f}ms')

 

결과

0.0532ms
0.0448ms
0.0448ms
0.0451ms

퀵 정렬의 장단점

 

장점

• 특정 상태(정렬된 상태)가 아닌 이상 평균 시간 복잡도는 O(nlogn)이며, 다른 O(nlogn) 알고리즘에 비해 대체적으로 속도가 매우 빠르다. 시간 복잡도가 O(nlogn) 정렬 알고리즘 중 분할 정복 방식인 병합정렬에 비해 2배 정도 빠르게 테스트 결과가 나왔다.
• 추가적인 별도의 메모리를 필요로 하지 않으며 재귀 호출 stack 프레임에 의한 공간 복잡도는 logn으로 메모리를 적게 소비함

 

단점

• 특정 조건(정렬된 상태)에서 성능이 떨어진다(O(n^2))
• 재귀를 사용하기 때문에 재귀를 사용하지 못하는 환경일 경우 그 구현이 매우 복잡해진다.