퀵 정렬(Quick sort)

1. 퀵 정렬이란?

• 기준점(Pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 에디터는 오른쪽으로 모아서 정렬을 하는 것
• 각 왼쪽, 오른쪽으로 나눈 것은 재귀 용법을 통해 다시 왼쪽, 오른쪽으로 나눔
• 반환하는 값은 [정렬된 왼쪽 리스트] + [Pivot] + [정렬된 오른쪽 리스트]

2. 알고리즘 구현

def qsort(data):
    if len(data) <= 1:
        return data
    left, right = list(), list()
    pivot = data[0]
    for index in range(1, len(data)):
    	if pivot > data[index]:
            left.append(data[index])
        else:
            right.append(data[index])
    return qsort(left) + [pivot] + qsort(right)

 

파이썬의 list comprehension을 사용한다면 위의 코드보다 짧게 구현이 가능해진다.

def qsort(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 qsort(left) + [pivot] + qsort(right)

 

3. 시간복잡도

일반적으로는 O(N logN)이지만, 최악의 경우인 맨 처음 pivot이 배열 내에서 가장 크거나 가장 작으면 모든 데이터를 비교하는 상황이 나오므로 O(N^2)이 될 수 있다.