[기술면접/알고리즘] Quick Sort

Quick Sort에 대해 설명하세요

Keyword

평균,최악,pivot

---

Script

퀵 정렬은 평균적으로 O(NlogN)의 시간복잡도를 가지는 정렬이며, 같은 시간복잡도의 다른 정렬 알고리즘보다 일반적으로 빠른 정렬 알고리즘입니다. 이는 퀵 정렬의 특성상 매 단계에서 적어도 1개의 원소가 자신의 자리를 찾게 되기 때문에, 단계를 거듭할수록 정렬할 개수가 줄어들기 때문입니다.

간단한 동작원리를 설명드리자면, 주어진 배열에서 하나의 값을 선택해 pivot이라 칭하고, 이를 기준으로 더 작은 값들과 더 큰 값들로 나누어 재귀적으로 정렬을 수행합니다.

하지만 이 경우, 이미 정렬되어있는 배열에서 맨 앞이나 뒤를 pivot으로 설정하게 되는 경우는 최악의 경우 O(n^2)의 시간복잡도를 가진다는 단점이 있습니다.

---

Additional

시간복잡도

BEST CASE
pivot에 의해 작은 쪽과 큰 쪽이 균형있게 나누어지는 경우

• 비교 횟수
  순환 호출의 깊이 = logN
  각 순환 호출 단계의 비교 연산 = N
  T(n) = O(NlogN)

WORST CASE
리스트가 계속 불균형하게 나누어지는 경우

• 비교 횟수
  순환 호출의 깊이 = N
  각 순환 호출 단계의 비교 연산 = N
  T(n) = O(N^2)

다른 정렬 알고리즘보다 빠른 이유

• 불필요한 데이터의 이동을 줄임
• 먼 거리의 데이터를 교환
• 한 번 결정된 피벗들이 추후 연산에서 제외됨

그림

코드 (python)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    lesser_arr, equal_arr, greater_arr = [], [], []
    for num in arr:
        if num < pivot:
            lesser_arr.append(num)
        elif num > pivot:
            greater_arr.append(num)
        else:
            equal_arr.append(num)
    return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)

정렬 알고리즘 시간복잡도 비교