정렬 알고리즘 : 퀵 정렬 (Python)

퀵 정렬

---

퀵 정렬 gif

개념

 '기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.' 퀵 정렬은 기준(피벗)을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 피벗을 고르는 기준은 가장 대표적으로 호어 분할(리스트에서 첫 번쨰 데이터를 피벗으로 정한다.)이 있다. 

 피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그다음 큰 데이터와 자긍ㄴ 데이터의 위치를 서로 교환해준다. 

 

1) 로직 : 분할 - 정복 - 결합

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

2) 상세 로직

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

소스 코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
        return array

    pivot = array[0] # 피벗은 첫 번째 원소
    tail = array[1:] # 피벗을 제외한 리스트

    left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print('result', quick_sort(array))

 

시간 복잡도

평균 시간 복잡도 : O(NlogN) // 선택, 삽입 정렬에 비해 매우 빠른 편이다.

최악의 경우 시간복잡도 : O(N^2)

 데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높다. 하지만 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, '이미 데이터가 정렬되어 있는 경우' 에는 매우 느리게 동작한다. 이런 경우엔 삽입 정렬을 쓰는 것이 적절하다.