퀵정렬

퀵 정렬은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다. 시간적 효율이 가장 중요한 정렬 알고리즘에서 이름 부터 "퀵"이라니. 그만큼 중요한 알고리즘이다.

"기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다."

퀵 정렬에서는 피벗(Pivot)이 사용된다. 위에서 말했다시피 큰 숫자와 작은 숫자를 교환할때 그 기준이 바로 피벗이다. 피버을 설정하고 리스트를 분할하는 방법에는 여러 가지 방식이 있다. 이 책에서는 가장 대표적인 분할 방식인 호어 분할 방식을 기준으로 퀵 정렬을 진행한다.

호어 분할 방식이란?

리스트에서 첫 번째 데이터를 피벗으로 정함.

데이터를 정렬하기 위해서 I 파트, II 파트, III 파트로 나누겠다.

I 파트

step 0

리스트의 첫 번째 데이터를 피벗으로 설정하므로 피벗은 '5'이다. 이 후 왼쪽에서부터는 피벗보다 큰 데이터를 선택하고, 오른쪽에서부터는 피벗보다 작은 데이터를 선택한다. 즉 왼쪽은 '7', 오른쪽은 '4'가 선택되고 두 개의 위치를 서로 변경한다.

step 1

그 다음 다시 피벗보다 큰 데이터와 작은 데이터를 각각 찾은 후 두 값의 위치를 서로 변경한다. 현재 '9'와 '2'가 선택됐으며, 두 위치를 서로 변경한다.

step 2

그 다음 다시 피벗보다 큰 데이터, 작은 데이터를 찾는다. 하지만 이번의 경우에는 왼쪽에서 찾는 값과 오른쪽에서 찾는 값의 위치가 서로 엇갈린 것을 볼 수 있다. 이렇게 두 값이 엇갈린 경우에는 작은 데이터와 피벗의 위치를 서로 변경한다.

step 3

이제 위치가 변경된 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트를 살펴보자. 왼쪽 리스트는 모든 원소가 피벗보다 작고, 오른쪽 리스트는 모든 원소가 피벗보다 큰 것을 볼 수 있다.
이렇게 피벗을 기준으로 작은 데이터를 왼쪽으로, 큰 데이터를 오른쪽으로 위치하도록 하는 작업을 분할(Divide)라 한다.

II 파트

왼쪽 리스트에서는 다음과 같이 동작한다.

오른쪽 리스트에서는 다음과 같이 동작한다.

array = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(array, start, end):
	if start >= end:  # 원소가 1개인 경우 종료
    	return
    pivot = start  # 피벗은 첫 번째 원소
    left = start + 1
    right = end
    while(left<=right):
    	# 피벗보다 큰 데이터를 찾을 때까지 반복
        while(left<=end and array[left]<=array[pivot]):
        	left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while(right>start and array[tight]>=array[pivot]):
        	right -= 1
        if(left>right):  # 엇갈렸다면 작은 데이터와 피벗을 교체
        	array[right], array[pivot] = array[pivot], array[right]
		else:  # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
        	array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)

quick_sort(array, 0, len(array)-1)
print(array)

파이썬의 장점을 살린 개선된 퀵 정렬

array = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(array):
	# 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
    	return array
    pivot = array[0]  # 피벗은 첫 번째 원소
    tail = array[1:]  # 피벗을 제외한 리스트
    
    left_side = [x for x in tail if x <= pivot]  # 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot]  # 분할된 오른쪽 부분
    
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행하고, 전체 리스트 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)
    
print(quick_sort(array))

퀵 정렬의 시간 복잡도

퀵 정렬의 시간 복잡도는 O(NlogN)이다.