Randomized Algorithms
알고리즘의 procedure 중 random한 어떤 선택이 들어가면 그것을 Randomized Algorithms이라고 한다.
Ex) BogoSort
- 아주 비효율적인 "무작위 섞기 → 확인" 알고리즘이다.
Ex) QuickSort
- 일반적인 퀵소트는 pivot을 무작위로 선택하면 Randomized QuickSort가 된다
이러한 랜덤 알고리즘엔 어떤 문제가 존재할까?
만약 어떤 나쁜 사람이 악의를 품고 랜덤값을 조작한다면 편향(biassed)된 값이 나올것이다.
뭐,,그렇다고 그냥
Bogo Sorting
사실 이 알고리즘은 밈에 가깝다. 그만큼 비효율적이라는 것
왜냐면 이 정렬 알고리즘은 입력을 랜덤하게 shuffle한다
언제까지? 정렬이 될때까지!
while True:
Random.shuffle(A) # 배열을 무작위로 섞는다
sorted = True
for i in range(len(A) - 1):
if A[i] > A[i+1]: # 정렬 안 되어 있으면
sorted = False
if sorted: # 정렬되어 있으면 종료
return A
→ 간단히 말하면, 무작정 랜덤하게 섞고 또 섞고 "정렬되어 있을 때까지 반복"하는 알고리즘이다.
당연히 실행시간의 예상값은 O(n·n!)이며 최약의 경우 끝없이 반복될(O(∞)) 수도 있다.
그러니 그냥 이런 알고리즘이 있긴하다~로만 알고 넘어가자
Quick Sort
본격적으로 이번 강의의 메인 내용인 퀵 정렬이다.
이 알고리즘은 이름에서도 알 수 있듯이 꽤나 빠른 알고리즘이라고 할 수 있다.
퀵 정렬의 핵심 아이디어는 다음과 같다.
🧠 핵심 아이디어 (Key Insight)
Choose a pivot and partition around it.
→ 임의의 피벗(pivot)을 선택하고, 피벗을 기준으로 작은 값/큰 값으로 나눈다.
이 과정은 배열을 두 부분으로 "분할(partition)"하는 작업이다.
Recursively apply quicksort to the sublists to the left and right of the pivot.
→ 피벗을 기준으로 왼쪽 부분과 오른쪽 부분 각각에 대해 재귀적으로 퀵 정렬을 적용한다.
💬 예시
배열 A = [9, 4, 6, 2, 8] 이 있다고 가정하자
**1. 랜덤하게 pivot으로 6을 선택했다고 가정한다.
-
partition:
왼쪽: [4, 2] (6보다 작은 값들)오른쪽: [9, 8] (6보다 큰 값들)
-
이제 [4, 2]와 [9, 8]에 대해 다시 quicksort를 재귀적으로 적용한다.
이걸 반복하면 결국 전체 배열이 정렬됩니다.**
의사코드
QUICKSORT(A, p, r):
if p < r:
q = PARTITION(A, p, r)
QUICKSORT(A, p, q - 1)
QUICKSORT(A, q + 1, r)
PARTITION(A, p, r)
x = A[r] // 피벗: 배열의 마지막 원소
i = p - 1
for j = p to r - 1: // p부터 r-1까지 검사
if A[j] ≤ x: // 피벗보다 작으면
i = i + 1
swap A[i] ↔ A[j]
swap A[i + 1] ↔ A[r] // 마지막에 피벗을 올바른 자리에 놓음
return i + 1 // 피벗의 최종 위치 반환
정확성 증명
🧱 Partition 함수의 루프 불변식
루프가 돌 때마다 다음 두 가지 조건은 언제나 성립해야 함:
1. A[p ... i] 구간의 모든 값은 pivot 이하
2. A[i+1 ... j-1] 구간의 모든 값은 pivot 초과
Quick sort 시간복잡도 분석
1. Best Case (Balanced Case)
피벗이 항상 "정확히 가운데" 요소일 때
즉, 배열이 거의 반반씩 나눠질 때가 퀵정렬의 베스트 케이스이다.
📌 재귀식: T(n)=2T(⌊n/2⌋)+Θ(n)
2T(n/2): 양쪽 반씩 정렬
Θ(n): partition 단계에서 전체 스캔
⏱ 시간복잡도: Θ(nlogn)
➡️ 병합 정렬과 같은 시간 복잡도!
2. Worst Case (Unbalanced Case)
피벗이 항상 가장 큰 값이나 가장 작은 값일 때가 워스트 케이스이다.
📌 재귀식: T(n)=T(n−1)+T(0)+Θ(n)=T(n−1)+Θ(n)
거의 한쪽만 정렬 → 재귀 깊이는 n이 된다
⏱ 시간복잡도 : Θ(n^2)
➡️ 삽입 정렬만큼 느려짐. (피벗 고르기 실패 시)
그럼에도 불구하고, 퀵정렬은 최악의 경우가 아닌이상, Θ(nlogn)의 시간복잡도를 가진다
피벗의 위치가 9대1로 계속 나뉘어진다 하더라도 말이다.
그렇다고해서 최악의 경우를 배제할수는 없을 노릇이다.
그래서 우리는 이를 해결하기 위한 방법을 다음 시간에 배워볼 것이다
