[정렬] quick sort

퀵 정렬은 말 그대로 대부분의 경우에 최상의 성능을 보여주는 정렬 기법이라고 할 수 있다.

정렬은 다음과 같이 이루어진다.

 

1. 리스트에서 임의의 한 원소를 pivot으로 하여, 이를 기준으로 두 리스트로 나눈다. 리스트의 크기는 다를 수 있다.

2. 왼쪽 리스트에는 pivot보다 작은작거나 같은 값만을, 오른쪽 리스트에는 pivot보다 큰크거나 같은 값만을 남긴다.

3. 왼쪽 리스트와 오른쪽 리스트에 대해서 quick sort를 수행한 후 이를 병합한다.

 

여기서 2번 과정은 다음과 같이 이루어진다. [3, 6, 1, 8, 5, 9, 4, 2, 7]을 예로 들고 pivot은 항상 첫 번째 원소라고 하자.

 

1. arr = [6, 1, 8, 5, 9, 4, 2, 7], pivot = arr[first] = 6, left = first = 1, right = last = 7 상태에서 시작한다.

pivot = 6보다 큰 값을 만날 때까지 left를 증가시킨다. -> left = 2

pivot = 6보다 작은 값을 만날 때까지 right를 감소시킨다. -> right = 6

(등호에 집착할 필요는 없다. 중복 원소를 고려하여 등호를 제거한다.)

arr[left]와 arr[right]를 swap한다.

 

2. arr = [6, 1, 2, 5, 9, 4, 8, 7], pivot = 6, left = 3, right = 5 상태에서 시작한다.

pivot = 6보다 큰 값을 만날 때까지 left를 증가시킨다. -> left = 4

pivot = 6보다 작은 값을 만날 때까지 right를 감소시킨다. -> right = 5

(등호에 집착할 필요는 없다. 중복 원소를 고려하여 등호를 제거한다.)

arr[left]와 arr[right]를 swap한다.

 

3. arr = [6, 1, 2, 5, 4, 9, 8, 7], pivot = 6, left= 4, right = 5 상태에서 시작한다.

pivot = 6보다 큰 값을 만날 때까지 left를 증가시킨다. -> left = 5

pivot = 6보다 작은 값을 만날 때까지 right를 감소시킨다. -> right = 4

left는 pivot보다 큰 값을 찾으므로 arr[first+1]~arr[left-1]은 무조건 pivot 이하이다.

right는 pivot보다 작은 값을 찾으므로 arr[right+1]~arr[last]는 무조건 pivot 이상이다.

이 때 swap(arr[first], arr[right])를 해주면,

arr[right]를 중심으로 왼쪽에는 arr[right] 이하의 값만, 오른쪽에는 arr[right] 이상의 값만 남아있게 된다.

return right를 해줌으로써 quick_sort()에서 right를 고정시켜놓고

왼쪽 및 오른쪽 배열에 대해서 다시 quick_sort()를 호출할 수 있다.

 

* i, j가 교차하면, i, j는 pivot을 기준으로 작은 값과 큰 값들의 경계에 위치한다!

 

def divide(arr, first, last):
    # left==right인 경우에 갱신된 pivot=arr[first]를 이용해야 하기 때문에,
    # 여기서 pivot=arr[first] 이런 식으로 선언해버리면 안 된다.
    left = first + 1
    right = last

    while (left <= right):
    # 원소가 2개인 경우, 처음부터 left==right이므로 등호가 포함되어야 한다.
        while arr[left] < arr[first] and left < last: left+=1
        # pivot과 arr[sth]이 같을 수 있으므로 등호가 포함되어서는 안 된다.
        # 이렇게 하면, 모든 왼쪽 원소는 arr[sth]<=pivot, 모든 오른쪽 원소는 arr[sth]>=pivot이 된다.
        while arr[right] > arr[first] and right > first: right-=1
        if left < right:
            arr[left], arr[right] = arr[right], arr[left]
        else:
            arr[right], arr[first] = arr[first], arr[right]
    
    return right
      
def quick_sort(arr, first, last):
    if first >= last: return
    
    mid = divide(arr, first, last)
    quick_sort(arr, first, mid-1)
    quick_sort(arr, mid+1, last)

##### test #####
def print_quick_sort(arr):
    quick_sort(arr, 0, len(arr)-1)
    print(arr)

print_quick_sort([1, 1])
print_quick_sort([1, 2])
print_quick_sort([2, 1])
print_quick_sort([1, 1, 1, 1, 1])
print_quick_sort([1, 2, 3, 4, 5])
print_quick_sort([5, 4, 3, 2, 1])
print_quick_sort([3, 1, 2, 3, 2, 1])