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
'📚 STUDY > 📈 알고리즘' 카테고리의 다른 글
BFS (너비 우선 탐색) (0) | 2025.05.07 |
---|---|
DFS (깊이 우선 탐색) (0) | 2025.05.07 |
Merge sort (0) | 2025.05.07 |
Divide-and-Conquer Algorithm (0) | 2025.04.15 |
Algorithm & Time Complexity (0) | 2025.04.15 |