Python 72 - 정렬 _ 기준에 따라 데이터를 정렬 (퀵 정렬)

퀵 정렬

퀵 정렬은 지금까지 배운 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다. 이 책에서 다루지는 않지만 퀵 정렬과 비교할 만큼 빠른 알고리즘으로 '병합 졍렬' 알고리즘이 있다. 이 두 알고리즘은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도 하다. 그렇다면 퀵 정렬은 도대체 어떻게 동작하길래 이름부터가 '빠른 정렬 알고리즘' 인지 알아보자.

 

'기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?'

 

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 이해하기까지 시간이 걸리겠지만 원리를 이해하면 병합 정렬, 힙 정렬 등 다른 고급 정렬 기법에 비해 쉽게 소스코드를 작성할수 있다.

퀵 정렬에서는 피벗(Pivot) 이 사용된다. 큰 숫자와 작은 숫자를 교환할 떄, 교환하기 위한 '기준'을 바로 피벗이라고 표현한다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분하는데 책에서는 가장 대표적인 분할 방식인 호어 분할(Hoare Partition)방식을 기준으로 퀵 정렬을 설명하겠다. 호어 분할 방식에서는 다음과 같은 규칙에 따라서 피벗을 설정한다.

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

이와 같이 피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다. 이러한 과정을 반복하면 '피벗'에 대하여 정렬이 수행된다. 자세한 과정은 그림으로 살펴보며 이해해보자. 다음과 같이 초기 데이터가 구성되어 있다고 가정해보자.

퀵 정렬은 전체를 3개의 파트로 나눠서 보는 게 편하다. 편의상 Ⅰ, Ⅱ, Ⅲ 파트로 나눠서 보겠다.

Ⅰ파트

이러한 상태에서 왼쪽 리스트와 오른쪽 리스트를 개별적으로 정렬시키면 어떨까? 어차피 왼쪽 리스트는 어떻게 정렬되어도 모든 데이터가 '5'보다 작다. 마찬가지로 오른쪽 리스트 또한 어떻게 정렬되어도 모든 데이터가 '5' 보다 크다. 따라서 왼쪽 리스트와 오른쪽 리스트에서도 각각 피벗을 설정하여 동일한 방식으로 정렬을 수행하면 전체 리스트에 대하여 모두 정렬이 이루어질 것이다.

Ⅱ파트

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

Ⅲ파트

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

이 과정은 종이를 잘라 숫자를 적은 다음에 직접 한번 해보기를 권한다. 그러면 더 빠르게 이해할 수 있으리라 본다. 

퀵 정렬에서는 이처럼 특정한 리스트에서 피벗을 설정하여 정렬을 수행한 이후에, 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각가 다시 정렬을 수행한다. 5장에서 다루었던 '재귀 함수'와 동작 원리가 같다. 실제로 퀵 정렬은 재귀 함수 형태로 작성했을 때 구현이 매우 간결해진다. 재귀 함수와 동작원리가 같다면, 종료 조건도 있어야 할 것이다. 퀵 정렬이 끝나는 조건은 언제일까? 바로 현재 리스트의 데이터 개수가 1개인 경우이다. 리스트의 원소가 1개라면, 이미 정렬이 되어 있다고 간주할 수 있으며 분할이 불가능하다. 따라서 이러한 과정을 전체적으로 살펴보면 다음과 같이 정리할 수 있다. 퀵 정렬을 처음 접한 독자라면 다음 그림에서의 분할 과정을 곧바로 이해하기는 쉽지 않겠지만, 곧이어 등장할 소스코드와 함께 살펴보면 비로소 이해 할 수 있을 것이다.

다음 소스코드 형태는 널리 사용되고 있는 가장 직관적인 형태의 퀵 정렬 소스코드이다.

퀵 정렬 소스코드

array = [5, 7, 9, 6, 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)

출력결과
[1, 2, 3, 4, 5, 6, 6, 7, 8, 9]

다음은 파이썬의 장점을 살려 짧게 작성한 퀵 정렬 소스코드다. 전통 퀵 정렬의 분할 방식과는 조금 다른데, 피벗 과 데이터를 비교하는 비교 연산 횟수가 증가하므로 시간면에서는 조금 비효율적이다. 하지만 더 직관적이고 기억하기 쉽다는 장점이 있다.

파이썬의 장점을 살린 퀵 정렬 소스코드

array = [5, 7, 9, 6, 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))

출력결과
[1, 2, 3, 4, 5, 6, 6, 7, 8, 9]

퀵 정렬의 시간 복잡도

이제 퀵 정렬의 시간 복잡도에 대해서 알아보자. 앞서 다룬 선택 정렬과 삽입 정렬의 시간복잡도는 O(N²)이라고 하였다. 선택 정렬과 삽입 정렬은 최악의 경우에도 항상 시간 복잡도 O(N²)을 보장한다. 퀵 정렬의 평균시간 복잡도는 O(NlogN)이다. 앞서 다루었던 두 정렬 알고리즘에 비해 매우 빠른 편이다. 퀵 정렬이 어떻게 평균적으로 O(NlogN)의 시간 복잡도를 가지는지 궁금할 수 있는데, 퀵 정렬의 시간복잡도에 대한 증명은 초보자가 다루기에는 간단하지 않다. 더불어 코딩테스트를 목적으로 하는 겨웅, 퀵 정렬의 시간 복잡도 증명에 대하여 자세히 알지 못해도 큰 무리가 없다. 따라서 책에서는 구체적인 증명보다는 직관적인 이해를 돕기 위한 설명에 초점을 맞추어 전개하고자 한다.

 

퀵 정렬에서 최선의 경우를 생각해보자. 피벗값의 위치가 변경되어 분할이 일어날 때마다 정확히 왼쪽 리스트와 오른쪽 리스트를 절반씩 분할한다면 어떨까? 데이터의 개수가 8개라고 가정하고 다음과 같이 정확히 절반씩 나눈다고 도식화를 해보자. 이때 '높이' 를 확인해보면, 데이터의 개수가 N개 일때 높이는 약 logN이라고 판단할 수 있다.

다시 말해 분할이 이루어지는 횟수가 기하급수적으로 감소하게 되는 것이다. 일반적으로 컴퓨터 과학에서 log의 의미는 밑이 2인 로그를 의미한다. 즉 log₂N 을 의미하며 데이터의 개수 N이 1,000 일 떄 log₂N은 10 가량이다. N = 1,000 일때 log₂N은 10가량이다. N = 1,000일 떄 log₂N ~ 10 은 상대적으로 매우 작은 수임을 이해할 수 있다.

데이터의 개수가 많을 수록 차이는 매우 극명하게 드러난다. 다음 표를 보면 데이터의 개수가 많을수록 퀵 정렬은 앞서 다루었던 선택 정렬, 삽입 정렬에 비해 압도적으로 빠르게 동작하리라 추측할 수 있다. 표는 '평균 시간 복잡도'를 기준으로 각 정렬 알고리즘이 데이터의 개수가에 따라 얼마나 많은 연산을 요구하는지를 보여주기 위해 작성되었으며, 엄밀한 연산 횟수 비교는 아니다.

데이터의 개수(N)	N² ( 선택 정렬, 삽입 정렬 )	Nlog₂N ( 퀵 정렬 )
N = 1,000	~ 1,000,000	~ 10,000
N = 1,000,000	~ 1,000,000,000,000	~ 20,000,000

일반적으로 컴퓨터 공학 학부에서 퀵 정렬을 공부할 때에는 퀵 정렬의 수학적인 검증에 대해서도 공부하지만, 코딩테스트를 준비하는 과정에서는 그림을 통해 직관적인 이해를 하는 것만으로도 충분하다.

다만, 퀵 정렬의 시간 복잡도에 대하여 한가지 기억해둘 점이 있다. 바로 평균적으로 시간 복잡도가 O(NlogN) 이지만 최악의 경우 시간 복잡도가 O(N²) 이라는 것이다. 데이터가 무작위로 입력되는 경우 퀵 정렬을 빠르게 동작할 확률이 높다. 하지만 이책에서의 퀵 정렬처럼 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, '이미 데이터가 정렬되어있는 경우' 에는 매우 느리게 동작한다. 앞서 다룬 삽입 정렬은 이미 데이터가 정렬되어 있는 경우에는 매우 빠르게 동작한다고 했는데, 퀵 정렬은 그와 반대된다고 이해할 수 있다.

그래서 실제로 C++ 와 같이 퀵 정렬을 기반으로 작성된 정렬 라이브러리를 제공하는 프로그래밍 언어들은 최악의 경우에도 시간 복잡도가 O(NlogN)이 되는 것을 보장할 수 있도록 피벗값을 설정할 때 추가적인 로직을 더해준다. 파이썬 또한 마찬가지로 뒤에 설명할 기본 정렬 라이브러리를 이용하면 O(NlogN)을 보장해주기 때문에 여러분은 크게 걱정하지 않아도 된다. 구체적인 로직에 관한 내용은 책에서 자세히 다루지는 않도록 하겠다.

 

 

 

 

---

본 포스팅은 ‘이것이 코딩 테스트다 with 파이썬’을 읽고 공부한 내용을 바탕으로 작성하였습니다.

 

 

 

작성자 : 엄코딩 eomcoding