[알고리즘] 퀵 정렬(Quick sort) 이해 with Python

 

이번 포스팅은 저번 포스팅의 버블 정렬에 이어 퀵 정렬에 대해 정리한 내용입니다.

퀵 정렬(Quick Sort)은 가장 널리 사용되는 정렬 알고리즘 중 하나이며,

이번 포스팅에서 퀵 정렬의 개념과 구동 방식, 그리고 파이썬으로 하는 구현 예제를 통해

퀵 정렬을 알아보겠습니다.

---

 

| 퀵 정렬(Quick Sort) 이해

- 퀵 정렬은 분할 정복(Divide and Conquer) 알고리즘의 대표적인 예로 

다음과 같은 단계로 나눌 수 있습니다. 

 

1. 분할(Divide) : 

• 리스트에서 하나의 요소를 선택, 이를 "피벗(Pivot)"이라 함
• 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮김

2. 정복(Conquer) :

• 피벗을 기준으로 분할된 두 리스트에 대해 재귀적으로 정렬 함수 호출
• 각 부분 리스트에 위 단계 반복

3. 결함(Combine) : 

• 재귀 호출이 끝나고 부분 리스트들이 결합
• 작은 값들은 왼쪽 리스트에, 큰 값들은 오른쪽 리스트에 모여 있음 
• 따라서 왼쪽 리스트 + 피벗 + 오른쪽 리스트 순서로 결합하여 정렬된 배열 얻음

- 그림으로 단계를 이해해 보겠습니다.

 

 

 

- 위 단계로 진행되는 퀵 정렬을 파이썬 코드로 구현해 보겠습니다.

 

예시) 재귀를 사용한 퀵 정렬 (피벗 선택 : 리스트의 첫 번째 원소)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[0]  # 첫 번째 원소를 피벗으로 선택
    left = []
    right = []

    for element in arr[1:]:
        if element < pivot:
            left.append(element)
        else:
            right.append(element)

    return quick_sort(left) + [pivot] + quick_sort(right)

# 퀵 정렬을 테스트해보기
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print(sorted_arr) # Output : [1, 1, 2, 3, 6, 8, 10]

 

예시) 반복 퀵 정렬 (피벗 선택 : 리스트의 중간 값)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    stack = []
    stack.append((0, len(arr) - 1))

    while stack:
        low, high = stack.pop()
        pivot_index = partition(arr, low, high)

        if low < pivot_index - 1:
            stack.append((low, pivot_index - 1))  # 왼쪽 부분 배열을 스택에 추가
        if pivot_index < high:
            stack.append((pivot_index, high))  # 오른쪽 부분 배열을 스택에 추가

def partition(arr, low, high):
    pivot = arr[(low + high) // 2]  # 중간 값을 피벗으로 선택
    while low <= high:
        while arr[low] < pivot:
            low += 1
        while arr[high] > pivot:
            high -= 1
        if low <= high:
            arr[low], arr[high] = arr[high], arr[low]  # 왼쪽과 오른쪽 요소 교환
            low += 1
            high -= 1
    return low

# 퀵 정렬을 테스트해보기
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr)
print(arr)

 

- 위 코드를 보시면 재귀를 사용한 퀵 정렬과 그렇지 않은 퀵 정렬 두 개의 코드를 예시로 만들었습니다.

이 두 가지 방법의 장단점을 확인해 보겠습니다.

 

| 퀵 정렬(Quick Sort)의 재귀 사용 장단점

1. 재귀적 퀵 정렬의 장단점 :

- 장점 : 

• 직관적인 구현 : 재귀를 사용한 퀵 정렬은 퀵 정렬의 단계를 가장 직관적으로 반영하여 코드의 직관성을 높여줍니다

- 단점 :

• 스택 관리의 어려움 : 재귀 호출을 사용할 경우 스택에서 오버플로우가 발생할 수 있습니다.
• 메모리 과다 사용 : 각 재귀 호출마다 스택 메모리가 생성되므로 메모리 사용량이 늘어납니다.

2. 반복적 퀵 정렬의 장단점 : 

- 장점 : 

• 스택 관리 쉬움 : 스택을 사용하지 않으므로 오버플로우 문제가 없습니다.
• 메모리 효율적 사용 : 재귀 호출이 없으므로 추가 메모리를 사용하지 않아 효율적으로 사용합니다.

- 단점 : 

• 복잡한 구현 : 재귀 호출을 사용하는 것보다 구현 및 이해의 어려움이 있습니다.

각각의 방법에 장단점이 존재하므로 상황에 따라 선택하여 구현하면 될 것 같습니다.

대부분의 상황에서는 재귀 퀵 정렬을 사용해도 문제가 없으며, 구현이 쉽고 간단합니다.

하지만 매우 큰 배열을 사용하는 경우는 재귀를 사용하지 않는 반복 퀵 정렬을 고려하면 좋을 것 같습니다.

---

| 퀵 정렬(Quick Sort) 특징

1. 평균 시간 복잡도 : O(n log n), 평균적으로 빠른 속도 제공

2. 최악 시간 복잡도 : O(n^2), 피벗 선택 전략에 따라 개선 가능

3. 불안정 정렬(Unstable Sorting) : 동일한 값에 대한 상대적인 순서 변경 

4. 피벗 선택 전략 : 피벗을 어떻게 선택하느냐에 따라 성능이 크게 달라짐 (중간 값을 선택하는 게 일반적)

---

| 마무리

- 퀵 정렬은 빠른 성능과 더불어 구현이 쉽다는 것을 알게 되었고 작동 원리에 대해 자세하게 알게 되었습니다.

핵심인 분할과 정복과 피벗을 중심으로 나누어 최종적으로 정렬된 배열을 얻는 방식이므로 자주 사용하게 될 것 같습니다.

 

틀린 점이나 질문이 있으시면 댓글로 남겨 주세요

 

다음 포스팅으로 찾아오겠습니다.

 

감사합니다 :)