[알고리즘] 퀵 정렬 Quick sort

퀵 정렬 Quick sort

• 분할 정복의 알고리즘 종류중 하나다 ( 분할 하여 정렬함)
• 정렬 알고리즘의 꽃으로 빠르다
  • 기준점(pivot)을 정해서, 기준점 보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right)로 모으는 함수를 사용
  • 각 왼쪽(left), 오른쪽(right)은  재귀용법을 사용해서 다시 동일 함수로 호출하여 위 작업을 반복함
  • return 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 

원리

list = [46, 97, 53, 3, 33, 65, 62, 52], Quick sort

1. pivot 선택

기본적으로 index 0을 pivot로 선택함

2. pivot을 기준으로 왼쪽(left)는 작은 수 오른쪽(right)는 큰 수로 둠, 나눈 것에 index 0을 pivot으로 둠

(분류된 데이터 수가 1개가 될때까지 분류함)

위의 과정을 반복하면

정렬된 list가 return 됨

---

코드

def qsort(num_list):  
    # 분류된 데이터가 1개 이하가 될 때까지
    if len(num_list) <= 1:
        return num_list
    
    left, right = list(), list()
    pivot = num_list[0]
    
    for i in range(1, len(num_list)):
        if pivot > num_list[i]:
            left.append(num_list[i])
        else:
            right.append(num_list[i])

    
    return qsort(left) + [pivot] + qsort(right)
    
    --------------------------------------------------
    
import random
a = random.sample(range(100),10)
qsort(a)

[15, 31, 21, 30, 45, 48, 22, 83, 11, 54]
-> [11, 15, 21, 22, 30, 31, 45, 48, 54, 83]

---

시간 복잡도

• 병합 정렬과 유사하지만 더 빠르다고 알려져 있음, \( O(nlogn) \)
• 최악의 상황의 경우 (모든 데이터를 비교하는 상황)
  • \( O(n^{2}) \)