[알고리즘/정렬] 퀵 정렬

0. 🔖 목차

1. 퀵 정렬 알고리즘
   1-1. 개념
   1-2. 알고리즘
   1-3. 복잡도

1. 퀵 정렬 알고리즘

1-1. 개념

퀵 정렬은 아래와 같은 방법으로 동작한다.

1. 리스트 가운데서 하나의 원소를 고른다(피벗)
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다
3. 분할된 두 개의 작은 리스트에 대해 리스트의 크기가 0이나 1이 될 때까지 반복

분할 정복의 일종이다.

1-2. 알고리즘

def quicksort(x):
    if len(x) <= 1:
        return x

    pivot = x[len(x) // 2]
    less = []
    more = []
    equal = []
    for a in x:
        if a < pivot:
            less.append(a)
        elif a > pivot:
            more.append(a)
        else:
            equal.append(a)

    return quicksort(less) + equal + quicksort(more)

1-3. 복잡도