[Algorithm]퀵정렬 알고리즘 완벽 가이드: 파이썬 예제와 함께 배우기

퀵정렬(Quick Sort)은 비교 기반의 정렬 알고리즘 중 하나로, 데이터의 분할 및 정복 기법을 이용해 효율적으로 정렬합니다. 이 글에서는 퀵정렬의 기본 개념부터 파이썬 예제를 통해 이해하고, 다양한 최적화 방법까지 다뤄보겠습니다.

≣ 목차

• 퀵정렬의 개념📚
• 퀵정렬 알고리즘의 단계별 설명📝
• 파이썬으로 퀵정렬 구현하기🐍
• 퀵정렬의 시간 복잡도⏱

---

01. 퀵정렬의 개념📚

퀵정렬(Quick Sort)은 비교 기반의 정렬 알고리즘 중 하나로, 평균적으로 매우 빠른 성능을 보이는 알고리즘입니다. 퀵정렬은 분할 정복(Divide and Conquer) 방법을 사용하여 배열을 정렬합니다. 퀵정렬의 기본 개념은 다음과 같습니다:

1. 기준 선택 (Pivot Selection): 배열에서 하나의 요소를 선택하여 기준점(Pivot)으로 삼습니다. 이 기준점은 배열을 두 부분으로 나누는 역할을 합니다.
2. 분할 (Partitioning): 기준점을 기준으로 배열을 두 부분으로 나눕니다. 기준점보다 작은 값들은 기준점의 왼쪽에, 큰 값들은 오른쪽에 위치하도록 재배열합니다. 이 과정을 통해 기준점은 최종 위치에 놓이게 됩니다.
3. 재귀적 정렬 (Recursive Sort): 기준점을 제외한 두 부분 배열에 대해 퀵정렬을 재귀적으로 수행합니다. 배열의 크기가 1 이하가 될 때까지 이 과정을 반복합니다.

퀵정렬의 과정은 다음과 같습니다:

1. 배열에서 기준점(Pivot)을 선택합니다.
2. 기준점을 기준으로 배열을 두 부분으로 나눕니다.
3. 왼쪽 부분과 오른쪽 부분을 각각 다시 퀵정렬합니다.
4. 모든 부분 배열이 정렬되면 전체 배열이 정렬됩니다.

퀵정렬의 장점과 단점은 다음과 같습니다:

장점

• 평균 시간 복잡도: O(n log n)으로 대부분의 경우 매우 빠릅니다.
• 제자리 정렬: 추가적인 메모리를 거의 사용하지 않습니다(재귀 호출에 사용되는 메모리를 제외하면).

단점

• 최악의 경우 시간 복잡도: O(n²)로, 배열이 이미 정렬되어 있거나 모든 요소가 동일한 경우에 발생할 수 있습니다.
• 불안정 정렬: 동일한 값의 요소들의 상대적인 순서가 보장되지 않습니다.

---

02. 퀵정렬 알고리즘의 단계별 설명📝

퀵정렬 알고리즘의 단계별 설명을 위해, 예시 배열 [3, 6, 8, 10, 1, 2, 1]을 사용하여 설명하겠습니다.

1. 기준점 선택 (Pivot Selection)

먼저, 배열에서 기준점을 선택합니다. 보통 첫 번째 요소, 마지막 요소, 중간 요소, 또는 무작위로 선택된 요소를 기준점으로 사용합니다. 이 예제에서는 첫 번째 요소 3을 기준점으로 선택하겠습니다.

2. 분할 (Partitioning)

기준점을 기준으로 배열을 두 부분으로 나눕니다. 기준점보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 위치하도록 재배열합니다. 이 과정을 통해 기준점은 최종 위치에 놓이게 됩니다.

분할 과정은 다음과 같습니다:

• 배열: [3, 6, 8, 10, 1, 2, 1]
• 기준점: 3

왼쪽부터 시작하여 기준점보다 큰 값을 찾고, 오른쪽부터 시작하여 기준점보다 작은 값을 찾습니다. 두 값을 교환합니다.

• 초기 상태: [3, 6, 8, 10, 1, 2, 1]
• 6 (기준점보다 큼)과 1 (기준점보다 작음)을 교환: [3, 1, 8, 10, 1, 2, 6]
• 8 (기준점보다 큼)과 2 (기준점보다 작음)을 교환: [3, 1, 2, 10, 1, 8, 6]
• 10 (기준점보다 큼)과 1 (기준점보다 작음)을 교환: [3, 1, 2, 1, 10, 8, 6]
• 최종 상태: [1, 1, 2, 3, 10, 8, 6]

이제 3은 배열의 네 번째 위치에 있으며, 왼쪽에는 3보다 작은 값들, 오른쪽에는 3보다 큰 값들이 위치합니다.

3. 재귀적 정렬 (Recursive Sort)

기준점을 제외한 두 부분 배열에 대해 퀵정렬을 재귀적으로 수행합니다.

왼쪽 부분 배열 [1, 1, 2]

• 기준점: 1
• [1, 1, 2]는 이미 1보다 작은 값과 큰 값으로 분할되어 있습니다.
• 다시 분할:
  • [1] (기준점보다 작음)과 [2] (기준점보다 큼)
• 최종 정렬: [1, 1, 2]

오른쪽 부분 배열 [10, 8, 6]

• 기준점: 10
• [10, 8, 6]은 이미 10보다 작은 값들로 구성되어 있습니다.
• 다시 분할: [8, 6] (기준점보다 작음)
• 최종 정렬: [6, 8, 10]

4. 최종 정렬

모든 부분 배열이 정렬되면 전체 배열이 정렬됩니다. 최종 배열은 [1, 1, 2, 3, 6, 8, 10]입니다.

요약

1. 기준점을 선택합니다.
2. 기준점을 기준으로 배열을 두 부분으로 분할합니다.
3. 각 부분 배열에 대해 재귀적으로 퀵정렬을 수행합니다.
4. 모든 부분 배열이 정렬되면 전체 배열이 정렬됩니다.

이 과정을 시각적으로 표현하면 다음과 같습니다:

[3, 6, 8, 10, 1, 2, 1]  --기준점: 3-->
[1, 1, 2, 3, 10, 8, 6]
[1, 1, 2] --기준점: 1--> [1, 1, 2]  [10, 8, 6] --기준점: 10--> [6, 8, 10]
최종 배열: [1, 1, 2, 3, 6, 8, 10]

---

03. 파이썬으로 퀵정렬 구현하기🐍

다음은 파이썬으로 퀵정렬을 구현한 예제입니다.

def median_of_three(arr):
    # 배열의 첫 번째, 중간, 마지막 요소를 선택합니다.
    first = arr[0]
    middle = arr[len(arr) // 2]
    last = arr[-1]
    # 세 요소를 정렬하여 중앙값을 반환합니다.
    return sorted([first, middle, last])[1]

def optimized_quicksort(arr):
    # 기본 사례: 배열의 길이가 1 이하인 경우 이미 정렬된 상태이므로 배열을 반환합니다.
    if len(arr) <= 1:
        return arr
    
    # 기준점을 median_of_three 함수를 사용하여 선택합니다.
    pivot = median_of_three(arr)
    
    # 기준점보다 작은 요소들로 이루어진 리스트를 만듭니다.
    left = [x for x in arr if x < pivot]
    
    # 기준점과 동일한 요소들로 이루어진 리스트를 만듭니다.
    middle = [x for x in arr if x == pivot]
    
    # 기준점보다 큰 요소들로 이루어진 리스트를 만듭니다.
    right = [x for x in arr if x > pivot]
    
    # 재귀적으로 각 부분 리스트를 정렬하고, 결합하여 최종 정렬된 리스트를 반환합니다.
    return optimized_quicksort(left) + middle + optimized_quicksort(right)

# 예시 배열
arr = [3, 6, 8, 10, 1, 2, 1]

# 최적화된 퀵정렬을 실행하고 결과를 출력합니다.
sorted_arr = optimized_quicksort(arr)
print(sorted_arr)

코드 설명:

1. median_of_three 함수:

• 배열의 첫 번째 요소 (first), 중간 요소 (middle), 마지막 요소 (last)를 선택합니다.
• 이 세 요소를 정렬하여 중앙값을 반환합니다. 이 중앙값이 퀵정렬의 기준점이 됩니다.

2. optimized_quicksort 함수:

• 기본 사례 처리: 배열의 길이가 1 이하인 경우, 배열이 이미 정렬된 상태이므로 그대로 반환합니다.
• 기준점 선택: median_of_three 함수를 사용하여 기준점을 선택합니다.
• 분할:
  - left 리스트: 기준점보다 작은 요소들로 구성된 리스트.
  - middle 리스트: 기준점과 동일한 요소들로 구성된 리스트.
  - right 리스트: 기준점보다 큰 요소들로 구성된 리스트.
• 재귀적 호출: left와 right 리스트에 대해 재귀적으로 optimized_quicksort 함수를 호출하여 각각을 정렬합니다.
• 결합: 정렬된 left 리스트, middle 리스트, 정렬된 right 리스트를 결합하여 최종 정렬된 배열을 만듭니다.

---

04. 퀵정렬의 시간 복잡도⏱

퀵정렬(Quick Sort)의 시간 복잡도는 피벗(pivot) 선택과 배열 분할이 얼마나 효율적으로 이루어지느냐에 따라 달라집니다. 퀵정렬의 시간 복잡도는 평균적으로 매우 효율적이지만, 최악의 경우에는 비효율적일 수 있습니다. 이를 구체적으로 살펴보겠습니다.

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

퀵정렬의 평균 시간 복잡도는 O(n log n)입니다. 이는 배열이 랜덤 하게 분포되어 있을 때, 각 분할 단계에서 배열이 대략 절반씩 나누어지기 때문에 발생합니다.

1. 분할 단계: 각 단계에서 배열을 두 부분으로 나눕니다.
2. 재귀 호출: 나눠진 두 부분 배열에 대해 재귀적으로 퀵정렬을 수행합니다.
3. 분할의 깊이: 배열이 절반씩 나뉘므로, 분할의 깊이는 log n 단계가 됩니다.
4. 각 단계의 작업량: 각 단계에서 모든 요소를 한 번씩 비교하므로, 각 단계의 작업량은 O(n) 입니다.

따라서, 평균적으로 log n 단계에서 각 단계마다 O(n)의 작업량이 필요하여 총 시간 복잡도는 O(n log n) 이 됩니다.

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

퀵정렬의 최악 시간 복잡도는 O(n²)입니다. 이는 피벗 선택이 항상 최악의 경우(예: 가장 작은 값 또는 가장 큰 값을 피벗으로 선택)로 이루어질 때 발생합니다.

1. 분할 단계: 각 단계에서 배열이 한쪽으로만 치우치게 나뉩니다.
2. 재귀 호출: 한쪽 배열의 크기는 계속 줄어들지만, 다른 쪽 배열은 거의 원래 크기와 동일하게 유지됩니다.
3. 분할의 깊이: 이 경우 분할의 깊이는 최대 n 단계가 됩니다.
4. 각 단계의 작업량: 각 단계에서 모든 요소를 한 번씩 비교하므로, 각 단계의 작업량은 O(n)입니다.

따라서, 최악의 경우 n 단계에서 각 단계마다 O(n)의 작업량이 필요하여 총 시간 복잡도는 O(n²) 이 됩니다.

최선 시간 복잡도: O(n log n)

퀵정렬의 최선 시간 복잡도도 O(n log n)입니다. 이는 피벗 선택이 항상 배열을 정확히 반으로 나누는 경우에 발생합니다. 이 경우는 평균 시간 복잡도와 동일합니다.

공간 복잡도

퀵정렬의 공간 복잡도는 일반적으로 O(log n) 입니다. 이는 재귀 호출 스택의 깊이에 따라 달라지며, 최악의 경우 O(n) 이 될 수 있습니다.

• 평균 및 최선의 경우: O(log n) (재귀 호출 스택의 깊이가 log⁡ n 이기 때문).
• 최악의 경우: O(n) (재귀 호출 스택의 깊이가 최대 n 이기 때문).

결론

• 평균 시간 복잡도: O(n log n)
• 최악 시간 복잡도: O(n²)
• 최선 시간 복잡도: O(n log n)
• 공간 복잡도: 평균적으로 O(log ⁡n), 최악의 경우 O(n)