[06정렬] 6-4 퀵정렬 (p165~170)

[퀵 정렬]

• 정렬 알고리즘 중 가장 많이 사용되는 알고리즘.
• "기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?"
  에서 시작
• 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작.
• 퀵 정렬에는 피벗(Pivot)이 사용됨. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 말함.

[시각화]

 

파트 1

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

 

step 1) 그다음 다시 피벗보다 큰 데이터와 작은 데이터를 각각 찾는다. 찾은 뒤에는 두 값의 위치를 서로 변경하는데, 현재 '9'와 '2'가 선택되었으므로 이 두 데이터의 위치를 서로 변경한다.

 

step2) 그 다음 다시 피벗보다 큰 데이터와 작은 데이터를 찾는다. 단, 현재 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈린 것을 알 수 있다. 이렇게 두 값이 엇갈린 경우에는 '작은 데이터'와 '피벗'의 위치를 서로 변경한다. 즉, 작은 데이터인 '1'과 피벗인 '5'의 위치를 서로 변경하여 분할을 수행한다.

 

step3) 분할 완료 이와 같이 피벗이 이동한 상태에서 왼쪽 리스트와 오른쪽 리스트를 살펴보자. 이제 '5'의 왼쪽에 있는 데이터는 모두 '5'보다 작고, 오른쪽에 있는 데이터는 모두 '5'보다 크다는 특징이 있다. 이렇게 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치하도록 하는 작업을 분할(Divide) 혹은 파티션(Partition)이라고 한다.

• 이렇게 정렬시, 왼쪽 리스트는 어떻게 정렬되어도 모든 데이터가 5보다 작으며,
  오른쪽 리스트 또한 어떻게 정렬되어도 5보다 크다.

 

파트2

step0) 왼쪽 리스트에서는 다음 그림과 같이 정렬이 진행되며 구체적인 정렬 과정은 동일하다.

 

파트3

step0) 오른쪽 리스트에서는 다음 그림과 같이 정렬이 진행되며 구체적인 정렬 과정은 동일하다.

 

• 이와 같이 퀵 정렬에서는 특정 리스트에서 피벗을 설정해 정렬을 수행한 이후, 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행함.
• 즉, 재귀 함수와 동작원리가 동일함.
• 재귀 함수라면 종료 조건이 있어야하는데, 종료 조건은 현재 리스트의 데이터 개수가 1개인 경우이다. 리스트의 원소가 1개라면 이미 정렬이 되어 있다고 간주할 수 있으며 분할이 불가능함.

 

[소스코드]

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[right] >= 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(N^2)이었음
• 퀵 정렬의 경우 평균적인 시간복잡도는 O(NlogN)이다.
• 그러나, 퀵 정렬의 최악의 경우 시간 복잡도는 O(N^2)이다.