퀵 정렬 (Quick Sort) - 파이썬

퀵정렬 간단정리

1. 불안정 정렬에 속하며, 다른 원소와의 비교로 정렬을 수행하는 비교정렬이다.

2. 분할정복 알고리즘의 하나이다.

3. 최선의 경우 O(nlogn)의 시간복잡도를 보이지만, 최악의 경우 O(n^2)의 시간 복잡도를 보인다.

4. 속도가 빠르고 추가 메모리 공간을 필요로 하지 않는다는 장점이 있다.

5. 정렬된 리스트에 대해서는 퀵정렬의 불균형 분할에 의해 수행시간이 오래 걸린다. 

 

과정

1. 리스트 안의 요소를 선택하고 이를 피벗(pivot)이라 한다.

2. 리스트를 순회하면서 피벗을 기준으로 피벗보다 작으면 피벗의 왼쪽에, 피벗보다 크다면 피벗의 오른쪽으로 옮긴다. 

3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다. (재귀)

4. 부분 리스트의 크기가 1이하가 되면 종료한다. 

 

파이썬 코드

def quick_sort(list):
    if len(list) <= 1:
        return list
    pivot = list[len(list) // 2]
    left = []
    right = []
    for i in list:
        if i < pivot:
            left.append(i)
        elif i > pivot:
            right.append(i)
    return quick_sort(left) + [pivot] + quick_sort(right)


num = [3, 5, 8, 1, 2, 7, 4, 0]
print(quick_sort(num))