퀵 소트

9.1 퀵 소트 정의

퀵 소트 (Quick Sort)는 "분할 정복" 접근 방식을 사용하는 효율적인 정렬 알고리즘이야. 이건 pivot 요소를 선택하고, 배열을 pivot보다 작은 요소들과 큰 요소들로 두 개의 하위 배열로 나누어서 각 하위 배열에 대해 재귀적으로 동일한 프로세스를 적용하는 방식으로 작동해.

퀵 소트 알고리즘은 "어떻게 하면 작은 요소들을 왼쪽으로, 큰 요소들을 오른쪽으로 최대한 빨리 보낼 수 있을까?"라는 문제를 해결하려는 시도로 등장했어. 예를 들어, 가장 작은 요소가 오른쪽 끝에 있다면, 그걸 어떻게 빨리, 비록 최종 위치는 아닐지라도 근접한 위치로 가져갈 수 있을까? 그렇게 한다면 불필요한 비교 횟수가 크게 줄어들 거야.

작동 원리:

1. Pivot 요소 선택:

배열에서 하나의 요소를 pivot으로 선택해. 이건 첫 번째 요소, 마지막 요소, 중간 요소, 혹은 랜덤 요소일 수도 있어. 때때로 세 개의 랜덤 요소의 산술 평균일 때도 있어.

2. 분할 (partitioning):

pivot보다 작은 모든 요소를 배열의 왼쪽으로, pivot보다 큰 모든 요소는 배열의 오른쪽으로 옮겨. 그 결과 pivot 요소는 정렬된 배열에서 자신의 최종 위치에 있게 돼.

재귀적 적용:

pivot 요소를 제외한 왼쪽과 오른쪽 하위 배열에 대해 재귀적으로 프로세스를 적용해.

단계별 프로세스

1. Pivot 요소를 선택해.
2. pivot보다 작은 요소를 왼쪽으로, 큰 요소를 오른쪽으로 옮겨.
3. 하위 배열에 대해 재귀적으로 프로세스를 적용해.

퀵 소트의 시간 및 공간 복잡도

시간 복잡도:

• 최악의 경우: O(n^2) — 매번 최악의 pivot 요소가 선택될 때 발생해 (예: 배열이 이미 정렬되어 있을 때).
• 평균적인 경우: O(n log n) — 무작위로 분포된 데이터에 대해서.
• 최선의 경우: O(n log n) — 배열이 매번 동일한 크기로 나누어질 때.

공간 복잡도:

O(log n) — 재귀 호출 스택을 저장하기 위해 필요한 공간이야, 만약 꼬리 재귀가 사용되고 pivot 요소들이 적절하게 선택된다면.

9.2 퀵 소트 알고리즘 구현

Python으로 구현:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr  # 기본 사례: 요소가 0 또는 1인 배열은 이미 정렬되었어
    
    pivot = arr[len(arr) // 2]  # Pivot 요소 선택
    left = [x for x in arr if x < pivot]  # Pivot보다 작은 요소들
    middle = [x for x in arr if x == pivot]  # Pivot과 같은 요소들
    right = [x for x in arr if x > pivot]  # Pivot보다 큰 요소들
    
    return quick_sort(left) + middle + quick_sort(right)

# 사용 예제:
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("정렬된 배열:", sorted_arr)
# 출력: 정렬된 배열: [1, 1, 2, 3, 6, 8, 10]

알고리즘의 작동 예제

배열 예제: [3, 6, 8, 10, 1, 2, 1]

첫 번째 패스:

• Pivot 요소: 8
• 왼쪽 요소들: [3, 6, 1, 2, 1]
• 중간 요소들: [8]
• 오른쪽 요소들: [10]

왼쪽 부분 [3, 6, 1, 2, 1]의 재귀적 정렬:

• Pivot 요소: 1
• 왼쪽 요소들: []
• 중간 요소들: [1, 1]
• 오른쪽 요소들: [3, 6, 2]

오른쪽 부분 [3, 6, 2]의 재귀적 정렬:

• Pivot 요소: 6
• 왼쪽 요소들: [3, 2]
• 중간 요소들: [6]
• 오른쪽 요소들: []

왼쪽 부분 [3, 2]의 재귀적 정렬:

• Pivot 요소: 2
• 왼쪽 요소들: []
• 중간 요소들: [2]
• 오른쪽 요소들: [3]

병합 결과: [1, 1, 2, 3, 6]은 왼쪽 부분에 해당하고, [10]은 오른쪽 부분에 해당하며, 중간은 [8]이야.

최종 정렬된 배열: [1, 1, 2, 3, 6, 8, 10]