Python Algorithm) quick sort (퀵정렬)

🎡 가장 빠른 정렬 👉 quick sort (퀵정렬)

💡 idea

1. pivot을 선택한다
2. pivot을 기준으로 비교데이터가 작으면 왼쪽, 크면 오른쪽에 배치한다.
3. 재귀적으로 정렬한다.

import random

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

data = random.sample(range(100),10)
print(quick_sort(data))
# [14, 19, 33, 56, 61, 65, 78, 79, 84, 90]

🤴 기왕 python 쓰는거 표현식으로 더 간결한 코드를 작성해보자

def quick_conph(data):
    if len(data) <= 1:
        return data
    pivot = data[0]
    left = [item for item in data[1:] if item < pivot]
    right = [item for item in data[1:] if item >= pivot]
    
    return quick_conph(left) + [pivot] + quick_conph(right)
    
data = random.sample(range(100),10)
print(quick_conph(data))
# [13, 20, 46, 55, 64, 72, 79, 81, 85, 86]

🎠 알고리즘 분석

• O(nlog(n)) - 빅오표기법은 최악의 시간을 가정하는 것이지만 이 경우는 평균적인 시간복잡도를 쓴다.
• Best의 경우, 피봇 양쪾으로 n/2씩 나눠진다고 가정하면 nlogn의 시간복잡도를 가진다.
• worst의 경우, 피봇이 한쪽으로 완전 치우쳐있을 때는 O(n^2)의 시간복잡도를 가진다.
  (일반적으로 병합정렬보다 빠르다.)

참고 : quick sort 시간복잡도 증명