[알고리즘] 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)란?

• 정렬 알고리즘의 꽃
• 기준점을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성한다.
• 각 왼쪽, 오른쪽의 데이터들은 재귀용법을 사용해서 위 과정을 반복한다.

퀵 정렬(Quick Sort) 이해

• 하나의 리스트를 기준점(pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽으로 분할하고, 기준점보다 큰 데이터는 오른쪽으로 분할한 다음, 정렬된 부분 리스트들과 기준점을 합하여 전체가 정렬된 리스트로 만들어준다.

 

퀵 정렬(Quick Sort) 구현

def quick_sort(data):
    pivot = data[0]
    left, right = list(), list()
    for i in range(1, len(data)):
        if pivot < data[i]:
            right.append(data[i])
        else:
            left.append(data[i])
    return quick_sort(left) + [pivot] + quick_sort(right)
    
    
# list comprehension을 이용하여 간단하게 작성하기
def quick_sort(data):
    pivot = data[0]
    left, right = list(), list()
    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)

 

퀵 정렬(Quick Sort) 시간 복잡도

• 시간복잡도는 O(nlogn), 병합정렬과 유사하다.
• 최악의 경우
• 맨 처음 pivot이 가장 작거나 가장 크면 모든 데이터를 비교하기 때문에 시간복잡도가 O(n^2)이 된다.