[Algorithm] Quick Sort, Quick Select, 3-way Partitioning

https://www.toptal.com/developers/sorting-algorithms

Sorting Algorithms Animations

위 사이트는 여러 정렬 기법의 속도를 비교할 수 있는 곳이다. 교수님께서 소개해주셨는데 여러 케이스를 한 눈에 볼 수 있어 매우 유용하다.

 

Quick Sort

기본 개념

정렬할 원소 중 하나를 기준값 v로 정한 후 <=v인 원소를 v의 왼쪽에, >=인 원소를 v의 오른쪽에 두는 분할을 반복 적용하는 정렬 방법이다. merge sort와 함께 정렬에서 가장 많이 쓰이는 방법이다. 

merge sort에 대해 알고 싶으면 아래 글을 참고하길 바란다.

2023.10.13 - [Computer Science/Data structure & Algorithm] - [Algorithm] Merge Sort

[Algorithm] Merge Sort

ㅣ본

 

Quick sort의 partition(분할) 과정은 아래 과정으로 진행된다.

배열 a[low ~ hi]에 담긴 값을 정렬해야한다고 하자.
1. 첫번째 원소 a[low] 를 기준값 v로 정한다.
2. 기준값을 제외한 배열의 양 끝에 포인터를 하나씩 둔다. (i, j = low+1, hi)
3. j <=i 가 될 때까지 아래 과정을 반복할 것이다. 
 - v보다 큰 a[i]가 나올 때 까지 i를 1씩 증가시킨다.
 - v 보다 작은 a[j]가 나올 때 까지 j를 1씩 감소시킨다.
 - a[i]와 a[j]를 swap한다.
4. 최종적으로 v와 a[j]를 swap한다

이렇게 배열의 첫번 째 값(=v)을 기준으로 더 작은 값은 왼쪽에 더 큰 값은 오른쪽에 배치한다. 그 다음 lo ~ v-1, v+1 ~ hi 까지 다시 partition을 하여 정렬하는 것을 크기가 1이 될 때까지 진행하면 된다. 

 

코드

def partition(a, lo, hi):
	i, j = lo+1, hi
    
    while True:
    	while i <= hi and a[i] < a[lo]: i = i+1
        while j >= lo +1 and a[j] > a[lo]: j = j+1
        
        if (j <= i): break
        a[i], a[j] = a[j], a[i]
        i, j = i+1, j-1
    a[lo], a[j] = a[j], a[lo]
    return j

 

 

성능(시간복잡도)

퀵 정렬의 가장 이상적인 상황은 partition을 정확하게 반으로 해서 깊이를 최소화 하는 것이다. 

그럼 가장 최악의 경우는 무엇일까? paritition을 했지만, 전혀 분할이 되지 않은 경우이다. 맨 앞의 값을 골랐는데 왼쪽, 오른쪽의 원소들이 한쪽으로 치우쳐져있는 경우를 의미하고 놀랍게도 이 경우는 '이미 정렬된 경우'이다. 

즉, 퀵 정렬은 이미 정렬된 경우를 정렬할 때 성능이 매우 좋지 않다.(~N^2 / 2)

 

이 상황을 막기 위해서는 처음에 random으로 값을 한 번 섞어주는 경우가 많다. 아니면 V의 값을 첫번째 값으로 고르지 않는 방법도 있다. 정말 간단한 아이디어지만, 이런 작은 trick으로 최악의 상황을 막는데 도움이 된다고 한다.

 

Quick Select

k Selection

크기 N의 배열이 주어졌을 때 k번째로 작은 원소를 찾을 것이다.  만약 k가 가장 작은 수(min 값) 이면 어떨까? min값은 배열을 한 번만 훑어서 찾을 수 있기 때문에 ~N이다. 

특수한 경우 말고 일반적인 상황이라면 가장 쉽게 생각할 수 있는 방법은 정렬을 한 뒤 k번째 원소를 찾으면 된다. 이 경우 ~NlogN이다. 

k selection을 NlogN보다 빠르게 할 수 있을까? 

우리는 quick sort의 개념을 사용하여 quick select를 할 것이다. 

 

Quick Select 기본개념

partition 하면 기준 값 a[j]는 정렬된 위치에 있다. 
j == k면 k 번째 원소를 찾았으므로 a[j]를 반환한다.
j < k 라면 오른쪽만 분할하고 k < j라면 왼쪽만 분할한다.

위 과정을 요약하면, quick select는 quick sort처럼 여러번 partition을 진행할 것인데 기준 값(v) 보다 내가 원하는 수의 위치가 더 위에 있으면 위쪽만 partition을 진행하는 방식이다. 

 

코드

def quickSelect(a, k):
	random.shuffle(a)
    
    lo, hi = 0, len(a)-1
    while(lo<hi):
    	j = partition(a, lo, hi)
        if j < k: lo = j+1
        elif k < j : hi = j-1
        else : return a[k]
    return a[k]

 

시간복잡도

average : N + N/2 + N/4 + .. + 1 = ~2N
N개 값을 분할하기 위해 N에 비례한 횟수의 비교/ 메모리 접근을 수행하면 된다. 

worst : ~N^2 / 2회

quick sort와 동일하게 random shuffle을 사용하면 worst case가 나올 확률은 벼락에 맞을 확률과 유사하다.

 

3-way Partitioning

중복된 값이 많은 데이터가 있다고 하자. 지금까지 배운 정렬 기법은 2-way paritioning이다. 기준값보다 작은 값이면 왼쪽, 크면 오른쪽 즉, 두 부분으로 나누었기 때문이다. 중복 데이터가 많으면, v 값과도 같은 결과가 많을 것이다. 

그럼, v 값과 같은 값(기준 값 속한 조각)을 제외하고 좌우 조각에 다시 partition을 적용하면 어떨까? (아래 그림 참고)

같은 값을 한 번에 추출해내기 때문에 중복된 값이 많을 수록 굉장히 이득적인 결과를 얻을 수 있다. 

 

def partition3Way(a, lo, hi):
	if (hi <= lo): return
		v = a[lo]
	lt, gt = lo, hi # Pointers to <v and >v sections
	i = lo
	while i <= gt:
		if a[i] < v:
			a[lt], a[i] = a[i], a[lt] # Swap
			lt, i = lt+1, i+1
		elif a[i] > v:
			a[gt], a[i] = a[i], a[gt] # Swap
			gt = gt-1
		else: i = i+1
    
    print(a)
	partition3Way(a, lo, lt-1)
	partition3Way(a, gt+1, hi)