Quick Sort

# Quick Sort

Quick Sort도 merge sort와 같이 분할과 합병을 하면서 정렬되는 벙식으로 수행됩니다.

퀵정렬은 pivot값을 정하는 것 부터 시작합니다. pivot은 배열의 젤 처음의 값이 될 수도 있고, 맨 끝값, 혹은 중앙값이 될 수 도 있습니다.

정한 pivot값을 기준으로 elements를 재배치하게 되는데, pivot의 왼쪽에는 pivot보다 작은값, 오른쪽에는 pivot보다 큰 값이 위치하게 됩니다. (이 과정에서pivot의 인덱스가 변할 수 있는데, pivot의 값 자체가 중요하기 때문에 pivot의 인덱스는 변해도 괜찮습니다.) 이때, 재배치된 왼쪽과 오른쪽 서브리스트들은 아직 정렬되지 않은 상태입니다. 한 번 정해진 pivot값은 이후 연산에서 제외됩니다.

이 서브리스트 안에서도 위와 같은 로직을 동일하게 적용해서, 서브리스트의 pivot값을 정하고 pivot을 기준으로 작은 값은 왼쪽에, 큰값은 오른쪽에 재배치해줍니다. 만약, 서브리스트의 크기가 1이 되면, 더이상 분할할 수 없습니다.

[ 시간복잡도 ] 

Quick sort도 merge sort와 같이 둘씩 분할하고 합병하는 과정을 거치기 떄문에, 평균 시간복잡도 O(NlogN)을 가집니다.

하지만, 모든 값들이 정렬된 리스트의 경우(최악의 경우) O(N^2)까지 시간복잡도가 늘어날 수 있습니다. 

이러한 치우친 분할을 극복하기 위해, pivot값을 고를 때, 몇가지의 후보군을 두고 그 중에 가장 중앙값을 찾아서 pivot으로 사용하는 방법을 사용하기도 합니다(*median of three)

 

Quick sort도 merge sort와 같이 시간복잡도 O(NlogN)을 가지지만, 같은 NlogN이더라도 실제 정렬에서는 훨씬 더 짧은 시간이 소요됩니다. 배열이 메모리 상에서 인접하게 위치해 있기 때문에 연산에서 유리한 것처럼, quick sort도 컴퓨터 하드웨어의 특성때문에 더 빠르다는 성질을 가질 수 있습니다. 이걸 참조 지역성의 원리로 설명하게 되는데, 퀵정렬은 알고리즘 특성상 동일한 배열 내에서 자리를 이동시킵니다. 그래서 인접한 데이터간의 이동이 생기기 때문에 제일 처음 배열에 접근할 때만 메모리에서 데이터를 가져오고 이후에는 캐시로 배열에 접근할 수 있기 때문에, 메모리로 접근할 때보다 훨씬 더 빠르게 접근 가능합니다.

한번 위치가 정해진 pivot이라는 기준값은 이후의 연산에서는 제외됩니다. 그렇기 때문에 정렬이 진행될수록(분할될수록) 계산해야할 데이터의 수가 점점 줄어들기 때문에 속도를 줄이는데에 영향을 줄 수 있습니다 그래서 퀵정렬은 merge정렬과는 다르게 추가적인 메모리공간을 사용하지 않는다는 특징이 있습니다 

 

 

# 코드 구현(Python)

우리는 pivot값을 중앙값으로 설정하고 코드를 구현할 것 입니다. 우선 sort에 의해 동작하는 함수QuickSort를 정의해줍니다.

def QuickSort(arr):
    Sort(arr, 0, len(arr)-1)

Sort함수는 리스트에서 가장 낮은 인덱스(0)와 가장 높은 인덱스(len(arr)-1)를 파라미터로 받아 동작합니다. 또한 Sort함수는 재귀호출하면서 devide&conquer을 구현합니다.

def Sort(arr, low, high):
    if low>=high:
        return
    pivot = (low+high)//2
    pivotvalue = arr[pivot]
    left = low
    right = high
    while left <= right:
        while arr[left]< pivotvalue:
            left += 1
        while arr[right]>pivotvalue:
            right -= 1
        if left <= right:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1
    Sort(arr, low, right)
    Sort(arr, left, high)

if low>=high:            mergesort와 마찬가지로 분할된 서브리스트의 크기가 1일때까지 반복하는 종료조건을 걸어줍니다.
    return
pivot = (low+high)//2       pivot은 리스트의 중앙값으로 설정한다고 했습니다.(pivot의 인덱스 값)
pivotvalue = arr[pivot]     pivot의 값을 기준으로 동작하기 때문에 value변수도 선언해줍니다.
left = low                         pivot의 왼쪽 left인덱스(초기 값은 가장 낮은 인덱스입니다)
right = high                      pivot의 오른쪽 right인덱스(초기 값은 가장 높은 인덱스 입니다)

pivot값이 설정되었으면 pivot값을 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽에 배치하는 작업을 해야합니다. 이는 while문을 통해 동작합니다.

while left <= right:              *위의 그림을 참고해 이해하시면 되겠습니다
    while arr[left]< pivotvalue:      pivot보다 작은 값 왼쪽배치(왼쪽값이 pivot보다 작으면 위치를 바꿔줄 필요가 없습니다)
        left += 1                             left인덱스 이동
    while arr[right]>pivotvalue:    pivot보다 큰 값 오른쪽배치(오른쪽값이 pivot보다 작으면 위치를 바꿔줄 필요가 없습니다)
        right -= 1                            right인덱스 이동
    if left <= right:                        왼쪽인덱스와 오른쪽인덱스가 교차하지 않는다면 두 값을 swap해줍니다.
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

while문을 통해 분할된 서브리스트에 대해서도 재귀함수를 사용해 분할을 진행합니다

 Sort(arr, low, right)               왼쪽 서브리스트   
 Sort(arr, left, high)                오른쪽 서브리스트

 

[ Test Code ]

if __name__ == '__main__':
    arr = [9,1,6,3,7,2,8,4,5,0]
    QuickSort(arr)
    print(arr)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

 

# 전체 코드

깃허브에서 테스트 코드를 포함한 전체 코드를 보실 수 있습니다.

GitHub - sonzwon/TIL: Today I Learned