[알고리즘/Algorithm] 파이썬으로 퀵 정렬(Quick Sort) 알아보기

Quick Sort (퀵 정렬)

• 기준점 (pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 기준점보다 큰 데이터는 오른쪽으로 모으는 함수를 작성
• 각 왼쪽, 오른쪽 데이터를 재귀 함수를 활용해서 다시 동일 함수를 호출하여 위 작업을 반복
  
  • 함수는 왼쪽, 오른쪽 데이터를 리턴

 

퀵 정렬 흐름

퀵 정렬은 위 그림과 같이 기준점(pivot)을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 정렬하고, 또 나뉘어진 값에서 왼쪽과 오른쪽으로

정렬하며 정렬될 때까지 반복하며 정렬하는 알고리즘이다.

 

파이썬으로 구현한 퀵 정렬 

def quick_sort(data):
    if len(data) <= 1:
        return data

    pivot = data[0]

    left = [item for item in data[1:] if pivot > item]
    right = [item for item in data[1:] if pivot <= item]

    return quick_sort(left) + [pivot] + quick_sort(right)

파이썬의 간결한 문법 + 리스트 컴프리헨션을 통해 위와 같은 가독성 좋은 퀵 정렬 알고리즘을 구현할 수 있다.

 

우선 기준점이 될 pivot은 리스트의 0번째 요소로 정했다.

그 후 리스트를 순회하면서 pivot 보다 작으면 왼쪽으로 모으고, 반대로 pivot 보다 크면 오른쪽으로 모은다.(여기서는 left와 right를 할당하는 코드에 해당한다)

이걸 return문에서 left, pivot, right를 재귀 함수로 반복해서 정렬하며 리스트를 합치면 자연스럽게 정렬된 리스트가 반환이 된다.

 

코드 자체는 파이썬의 문법의 힘을 빌려 매우 간단하나, 재귀 함수에 대한 이해가 없으면 쉽게 이해가 안 될 수 있다.

 

함수 실행 결과

target = [6, 7, 1, 2, 6, 1, 1, 5, 5, 6, 10, 123, 5451, 3123, 5, 1, 2, 3123, 423123, 4123, 1234]
print(quick_sort(target))
# [1, 1, 1, 1, 2, 2, 5, 5, 5, 6, 6, 6, 7, 10, 123, 1234, 3123, 3123, 4123, 5451, 423123]

 

시간 복잡도

• 기본적으로는 O(n log n)
• 단, 최악의 경우:
  • 맨 처음 pivot이 가장 크거나, 가장 작으면 모든 데이터를 비교해야 하며 이 경우에는 O(n^2)가 된다.