[Python] Quick sort. 파이썬에서 간단히 퀵 정렬 구현

퀵 정렬은 이름에서 알 수 있듯이 정렬 알고리즘 중 속도가  빠른 알고리즘이다.

퀵 정렬.gif

이해가 쉽고 간단한 정렬 알고리즘인 선택 정렬과 삽입 정렬의 시간 복잡도가 O(N^2) 인 것에 비해 퀵 정렬의 평균 시간 복잡도는 O(NlogN)이다.

아이디어는 다음과 같다.

• 기준이 되는 데이터인 pivot을 하나 선택한다.
  • 일반적으로 가장 많이 사용되는 것은 주어진 array의 첫 번째 요소이다. (array[0])
• pivot을 기준으로 pivot 보다 작은 데이터와 pivot보다 큰 데이터로 구분한다.
• pivot을 pivot보다 작은 데이터와 pivot보다 큰 데이터 사이에 위치시키면 pivot의 위치가 결정된다.
  • [pivot 이하] [pivot] [pivot 초과]
• pivot보다 작은 데이터와 pivot보다 큰 데이터 각각에서 동일하게 퀵 정렬을 수행한다. (재귀적으로)

퀵 정렬 설명

위 gif 이미지에서 보면 노란색이 pivot, 초록색이 pivot보다 작은 데이터, 보라색이 pivot보다 큰 데이터, 주황색이 정렬이 완료된 데이터이다.

이런 알고리즘을 기반으로 작성된 퀵 정렬 소스코드는 다음과 같다.

# 가장 일반적인 퀵 정렬
def quick_sort(array, start, end):
    if start >= end: return # 원소가 1개인 경우
    pivot = start # 피벗은 첫 요소
    left, right = start + 1, 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[right], array[left] = array[left], array[right]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

 

하지만 파이썬의 장점을 살려 훨씬 직관적이고 이해하기 쉬운 코드도 존재한다.

바로 다음과 같다.

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

# 파이썬의 장점을 살린 퀵 정렬
def quick_sort(array):
    # 리스트가 하나 이하의 원소를 가지면 종료
    if len(array) <= 1: return array
    
    pivot, tail = array[0], array[1:]
    
    leftSide = [x for x in tail if x <= pivot]
    rightSide = [x for x in tail if x > pivot]
    
    return quick_sort(leftSide) + [pivot] + quick_sort(rightSide)

동일하게 pivot에 array의 첫 번째 요소를 넣고, pivot을 제외한 나머지 데이터를 tail로 지정했다.

그리고 leftSide에 tail 중 pivot보다 작거나 같은 데이터를, rightSide에 tail 중 pivot보다 큰 데이터를 저장하고,

quick_sort(leftSide) + [pivot] + quick_sort(rightSid) 로 pivot의 위치를 정의하면서 재귀적으로 왼쪽, 오른쪽 부분을 다시 퀵 정렬하는 알고리즘이다.

왼쪽, 오른쪽 부분으로 나누는 부분에서 일반적인 방법보다 더 많은 비교 연산이 필요해 시간 면에서 조금 비효율적이지만 더 직관적이고 이해하기 쉽기 때문에 알아두면 좋을 것 같다.