퀵정렬의 특징, 복잡도, 파이썬 코드

퀵정렬의 개념

퀵정렬은 말 그대로 빠른 정렬 알고리즘입니다. 정렬할 데이터를 두 개의 그룹으로 나눠서 처리하는데요, 이때 기준이 되는 '피벗(pivot)'을 중심으로 데이터를 나누어 정렬하는 방식이죠. 쉽게 말해, 기준 키(피벗)를 정한 다음, 그 피벗보다 작은 값들은 앞쪽으로, 큰 값들은 뒤쪽으로 보내면서 데이터를 정렬하는 방식이에요. 이를 재귀적으로 계속 나눠서 정렬을 진행하죠.

퀵정렬의 시간복잡도

1. 평균 시간복잡도: O(n log n)  

대부분의 경우 평균적으로 이 정도 성능을 보입니다. 그래서 대규모 데이터를 처리할 때에도 속도가 꽤 빠른 편이에요.

2. 최악의 시간복잡도: O(n²)  

하지만 최악의 경우도 있습니다. 이때는 피벗이 극단적인 값으로 계속 선택되어 한쪽으로만 분할될 때인데요, 예를 들어 이미 정렬된 배열에 피벗이 항상 가장 큰 값이나 작은 값으로 선택된다면, 성능이 크게 떨어지죠. 그렇지만 적절한 피벗 선택 방법을 통해 이 최악의 경우는 회피할 수 있습니다.

퀵 정렬의 예제

예를 들어 볼까요? 다음과 같은 숫자들이 있다고 가정해봅시다.

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

피벗으로 5를 선택했다고 하면, 5보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽으로 이동시키게 됩니다.

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

이제 5를 기준으로 양쪽의 배열도 같은 방식으로 정렬하는 거예요. 이 과정을 재귀적으로 반복하면서 배열 전체가 정렬되는 것이 퀵정렬의 핵심이랍니다!

퀵정렬의 특징

1. 속도: 퀵정렬은 평균적으로 O(n log n)이라는 시간복잡도를 가지기 때문에, 데이터가 많아도 빠르게 처리할 수 있어요. 특히 배열이 크면 클수록 다른 알고리즘보다 빠르게 동작하죠. 그래서 실제로 현업에서 가장 많이 사용되는 정렬 알고리즘 중 하나입니다.

2. 재귀적 구조: 퀵정렬은 재귀적인 알고리즘입니다. 즉, 큰 문제를 작은 문제로 계속 나누어서 푸는 방식이에요. 그래서 코드 구현도 상대적으로 간단하답니다.

3. 제자리 정렬(in-place sorting): 퀵정렬은 별도의 메모리 공간을 거의 사용하지 않는 제자리 정렬입니다. 이 덕분에 메모리 효율도 좋아서 대규모 데이터를 처리할 때도 유리해요.

4. 불안정한 정렬(unstable sort): 퀵정렬은 같은 값이 있을 때 그 순서가 보장되지 않아요. 그래서 안정적인 정렬이 필요한 경우라면 퀵정렬보다 다른 방법을 사용하는 것이 좋습니다.

물론 퀵정렬에도 단점이 존재합니다. 그중 하나가 최악의 경우 시간복잡도가 O(n²)이라는 점인데요. 이미 정렬된 배열이나 거의 정렬된 배열에서는 성능이 크게 떨어질 수 있습니다. 그래서 피벗을 잘 선택하는 것이 중요하죠. 또한 퀵정렬은 재귀적인 특성 때문에 스택 오버플로우(Stack Overflow)가 발생할 수 있습니다. 매우 큰 배열을 정렬할 때에는 재귀 호출의 깊이가 깊어질 수 있어서, 스택 메모리 부족 문제가 생길 수 있다는 점도 주의해야 해요.

퀵정렬 파이썬 코드

def quicksort(x):
    if len(x) <= 1:
        return x

    pivot = x[len(x) // 2]
    less = []
    more = []
    equal = []
    for a in x:
        if a < pivot:
            less.append(a)
        elif a > pivot:
            more.append(a)
        else:
            equal.append(a)

    return quicksort(less) + equal + quicksort(more)