퀵 정렬 (Quick Sort)

퀵 정렬(Quick Sort)은 매우 효율적인 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 기법을 사용하여 리스트를 정렬한다. 퀵 정렬은 평균적으로 O(n log n)의 시간 복잡도를 가지며, 대부분의 경우 매우 빠르게 동작한다. 다만, 최악의 경우 시간 복잡도는 O(n^2)이 될 수 있다.

동작 원리

퀵 정렬은 다음과 같은 단계를 따른다:

1. 피벗 선택 (Pivot Selection): 리스트에서 하나의 요소를 선택한다. 이 요소를 피벗(pivot)이라고 한다.
2. 분할 (Partitioning): 피벗을 기준으로 리스트를 두 부분으로 나눈다. 피벗보다 작은 요소들은 피벗의 왼쪽에, 피벗보다 큰 요소들은 피벗의 오른쪽에 위치하게 한다.
3. 재귀적 정렬 (Recursive Sorting): 분할된 두 부분 리스트에 대해 재귀적으로 퀵 정렬을 수행한다.

알고리즘 단계

1. 피벗을 선택한다.
2. 리스트를 피벗을 기준으로 두 부분으로 분할한다.
3. 피벗을 기준으로 왼쪽 부분 리스트와 오른쪽 부분 리스트에 대해 재귀적으로 퀵 정렬을 수행한다.

예제

정렬할 리스트: [3, 6, 8, 10, 1, 2, 1]

1. 피벗 선택:
   • 피벗: 3 (리스트의 첫 번째 요소를 피벗으로 선택)
2. 분할:
   • 피벗보다 작은 요소: [1, 2, 1]
   • 피벗보다 큰 요소: [6, 8, 10]
   • 피벗 포함 리스트: [1, 2, 1, 3, 6, 8, 10]
3. 재귀적 정렬:
   • 왼쪽 부분 리스트 [1, 2, 1]에 대해 재귀적으로 퀵 정렬 수행
   • 오른쪽 부분 리스트 [6, 8, 10]에 대해 재귀적으로 퀵 정렬 수행

시간 복잡도

퀵 정렬의 시간 복잡도는 다음과 같다:

• 최선의 경우 (Best Case): O(n log n)
  • 리스트가 항상 균등하게 분할되는 경우이다.
• 평균 경우 (Average Case): O(n log n)
  • 대부분의 경우 퀵 정렬은 매우 빠르게 동작한다.
• 최악의 경우 (Worst Case): O(n^2)
  • 리스트가 이미 정렬되어 있거나 모든 요소가 같은 경우이다. 이 경우 피벗이 항상 리스트의 최대 또는 최소 값이 되어 비효율적으로 동작한다.

공간 복잡도

퀵 정렬은 제자리 정렬(in-place sorting) 알고리즘으로, 추가적인 메모리를 거의 사용하지 않기 때문에 공간 복잡도는 O(log n)이다. 이는 재귀 호출의 깊이에 의해 결정된다.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = [x for x in arr if pivot > x]
    middle = [x for x in arr if pivot == x]
    right = [x for x in arr if pivot < x]
    return quick_sort(left) + middle + quick_sort(right)

arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("Sorted array is:", sorted_arr)

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms