[알고리즘] I-4. 퀵소트 (Quicksort)

1. 탄생배경

(정렬 알고리즘들의 탄생 배경은 사실 특별한 것이 별로 없다. 자료구조 같은 경우 처음 의도와 현재 상용되는 방식과 다른 경우가 가끔 있지만 정렬 알고리즘들은 말 그대로 "정렬"을 위해 생겨난 것들로 탄생배경에 대한 자세한 이해가 공부에 큰 영향을 주지는 않을 것 같다. 참고 정도만 해도 충분할 것이라 생각한다.)

 

퀵소트는 1961년 영국의 컴퓨터과학자 Tony Hoare에 의해 고안되었다. 당시 기계번역 프로젝트를 하고 있었는데 입력받은 러시아어 문장을 자동으로 번역하는 과정이었다. 당시 전산화(?)된 사전은 자기 테이프 (magnetic tape)에 알파벳순으로 저장된 형태였는데 효율적인 사전 검색을 위해 입력받은 문장의 단어들을 알파벳 순으로 정렬하는 과정이 필요했다. 일차적으로 개발한 알고리즘은 바로 삽입정렬(insertion sort) 였지만, 시간복잡도가 O(n^2)인것을 알고 바로 다른 방법을 생각해냈는데 이것이 바로 퀵소트다.

2. 이해하기

2-1. 기본 로직

퀵소트의 기본 원리는 "현재 원소의 제자리 찾기" 라고 할 수 있다.

이 리스트는 정렬이 되지 않았지만, 5를 기준으로 왼쪽의 모든 원소들은 5보다 작으며, 오른쪽의 모든 원소들은 5보다 크다. 이 리스트가 전체 정렬이 되어있을 때와 현재 상태에서의 5의 위치가 다르지 않다는 것, 즉 5는 "제자리에 있다"는 것이다. 퀵소트는 리스트의 모든 원소들의 제자리를 찾는 알고리즘이다.

 

2-2. 직관적으로 이해하기

예시를 통해 퀵소트가 어떻게 작동하는지 알아보자.

 

1) 파티션 (Partition) 과정

pivot보다 큰 값을 만날때까지 i는 증가, pivot보다 작은 값을 만날때까지는 감소 시킨다.

앞서 언급한 조건을 만족하면 i 와 j를 swap한다,

i의 7은 pivot보다 크고 j의 5는 pivot보다 작다.

swap 한다.

i의 8은 pivot보다 크고, j의 1은 pivot 보다 작다.

 

swap 한다.

i가 j보다 커질 때 종료한다.

pivot인 6은 제자리를 찾았다. 정렬된 pivot을 기준으로 오른쪽, 왼쪽을 나누어 다시 동일한 과정을 반복한다.

이 일련의 과정을 파티션이라고 한다. 해당 과정을 거치면 설정한 pivot의 값은 제자리에 위치하게 된다. 파티션 과정이 끝나면, 제자리를 찾은 pivot을 기준으로 왼쪽 리스트와  오른쪽 리스트를 또 다시 partition한다. 이 과정을 더 이상 분할 할 수 없을 때까지 반복한다. 파티션을 짧게 정리하면 다음과 같다.

 

1) pivot은 리스트의 가장 첫 원소로 한다. (pivot의 위치에 대해선 뒤에 더 자세히 다루도록 하겠다.)

2) i를 리스트의 처음으로 지정하고 pivot값보다 큰 것을 찾을 때까지 1씩 증가시키면서 탐색한다. 찾으면 멈춘다.

3) j를 리스트의 끝으로 지정하고 pivot값보다 작은 것을 찾을 때까지 1씩 감소시키면서 탐색한다. 찾으면 멈춘다.

4) 이때의 i 와 j의 원소를 swap 한다.

5) 1~4의 과정을 j < i 가 되기까지 계속한다.

6) j < i 가 될 때 pivot 과 j 를 swap 한다. pivot은 이제 제자리에 위치하였다.

 

2) 전체 과정

리스트의 모든 원소들이 정렬이 될 때까지 파티션을 하는 과정

3.  퀵소트 분석

1) 퀵소트 분류

· 비교 정렬 (comparsion sort)

· 불안정 정렬 (not a stable sort)

· In-place 정렬

· 분할 정복 (Divide and Conquer) 기법의 알고리즘

 

2) 시간복잡도

· 최선

O(nlogn)

· 최악

O(n^2)

· 평균

O(nlogn)

3) Pivot

· 리스트의 가운데

· 랜덤하게

http://rabbit.eng.miami.edu/class/een511/quicksort.pdf

4. 소스코드

def quick_sort(nums, low, high):
    if low >= high:
        return
       
    pivot_index = partition(nums, low, high)
    quick_sort(nums, low, pivot_index - 1)
    quick_sort(nums, pivot_index + 1, high)
    
def partition(nums, low, high):
    pivot_index = (low + high) // 2
    swap(nums, pivot_index, high)
    
    i = low
    
    for j in range(low, high, 1):
        if(nums[j] <= nums[high]):
            swap(nums, i, j)
            i = i + 1
        
    swap(nums, i, high)
    
    return i
    
def swap(nums, i, j):
    temp = nums[i]
    nums[i] = nums[j]
    nums[j] = temp
    
if __name__ == "__main__":
    nums = [-2, -1, 0, 1, 0, -1, -2]
    quick_sort(nums, 0, len(nums)-1)
    print(nums)