퀵 정렬

퀵 정렬 (Quick Sort)

💡 퀵 정렬(Quick Sort)은 효율적인 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 방식을 사용하여 배열을 정렬합니다.

 

작동 원리

http://algorithm.wiki/ko/app/

 

1. 배열에서 하나의 원소를 선택합니다. 이 원소를 '피벗(pivot)'이라고 합니다.
2. 피벗을 기준으로 배열을 두 부분으로 나눕니다: 피벗보다 작은 원소들의 부분 배열과 피벗보다 큰 원소들의 부분 배열.
3. 각 부분 배열에 대해 재귀적으로 퀵 정렬을 수행합니다.
4. 모든 부분 배열이 원소 하나만을 가질 때까지 위의 과정을 반복합니다.

시간 복잡도

• 최선의 경우와 평균적인 경우: O(nlogn)
• 최악의 경우: O(n2) (이미 정렬된 배열이나 역순으로 정렬된 배열에서 피벗 선택이 잘못될 경우)

공간 복잡도

• 평균적인 경우: O(logn)
• 최악의 경우: O(n)

장단점

• 장점
  • 평균적으로 매우 빠르다.
  • 추가적인 메모리를 거의 사용하지 않는다 (in-place 정렬).
• 단점
  • 최악의 경우 시간 복잡도가 O(n2)이다.
  • 안정성(stable)을 보장하지 않는다.

 

구현

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    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 quick_sort(left) + middle + quick_sort(right)