Quick sort

Divide-and-conquer를 기반으로 하는 정렬 알고리즘으로, 방식은 아래와 같다.

1. Pivot 선택 : 배열에서 하나의 원소를 pivot으로 선택한다. 

2. 분할 : pivot을 기준으로 pivot보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 배열한다.

3. 재귀 호출 : 왼/오른쪽 부분 배열에 quick sort를 재귀적으로 수행한다.

 

💡 이상적인 경우

pivot이 항상 배열을 거의 절반으로 나누는 경우, T(n) = 2T(n/2)+O(n) 재귀식을 따른다.

마스터 정리를 이용하면, T(n)=O(nlogn)이 된다.

 

💡 최악의 경우

pivot이 항상 가장 작거나 or 큰 원소를 선택하는 경우이다.

(= 배열이 거의 정렬되어 있거나 역순일 때 잘못된 pivot을 선택한다는 말)

이때, partition은 배열을 거의 한 쪽으로만 나누어, 분할 결과 크기가 (n-1)인 부분과 0인 두 부분 배열로 나뉘게 된다.

이런 상황이 반복되면, 정렬해야 할 배열의 크기가 한 번에 1씩 줄어들게 된다.

따라서, T(n) = T(n-1)+O(n)이다.

* T(n-1) : 크기가 (n-1)인 부분 배열에 대해 다시 quick sort를 수행하는 시간

* O(n) : 현재 단계에서 pivot을 기준으로 분할하는데 드는 시간

 

T(n) = T(n-1)+cn

        = (T(n-2)+c(n-1)) + cn 

        = ((T(n-3)+c(n-2))+c(n-1)) + cn 

        = ...

        = T(1) + c(2+3+4+...+(n-1)+n)

T(1)은 상수시간 O(1)이라고 가정할 수 있어 무시하면, T(n) = c(2+3+...+n) = (n-1)(n-2)/2

즉, T(n) = O(n²)

 

✅ 제일 중요한 건, pivot을 선택하고 left, right를 판단하는 과정은 ⭐pivot의 위치를 찾는 것이라는 것.

 

 

(정렬하기 전, pivot을 기준으로 left, right를 나누고 언제 바꿀지 판단할 때 L > R로 두거나 L >= R로 두거나에 따라 방법이 있더라고요..)

(처음 들어봤는데 일단 정리를 해보겠습니다)

 

💡 Quick sort의 파티션 방식은 2가지가 있다.

1. Hoare Partition Scheme (호어 분할 방식)

✔ 조건 : left < right 일 때 계속 진행

✔ 교차 조건 : left >= right 이면 종료

- pivot 기준으로 좌/우에서 이동하며 엇갈리는 값을 교환

- pivot이 항상 중간으로 오진 않음

- 효율적이고, 평균적으로 교환 횟수가 적음.

while True:
    while arr[left] < pivot:
        left += 1
    while arr[right] > pivot:
        right -= 1
    if left >= right:
        return right
    swap(arr[left], arr[right])
    left += 1
    right -= 1

 

 

2. Lomuto Partition Scheme (로무토 분할 방식)

✔ 조건 : 보통 left <= right 형태

✔ 교차 조건 : left > right 이면 종료

- pivot은 보통 마지막 우너소

- pivot보다 작은 값들을 왼쪽으로 몰아넣고, 마지막에 pivot을 적절 위치로 옮김

- 단순하지만, 교환 횟수가 많아질 수 있음.

pivot = arr[high]
i = low - 1
for j in range(low, high):
    if arr[j] <= pivot:
        i += 1
        swap(arr[i], arr[j])
swap(arr[i+1], arr[high])
return i + 1