[python]퀵 정렬

퀵 정렬(Quick Sort)이란?

---

퀵 정렬은 기준(Pivot)을 먼저 정하고 그 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트들을 기준과 비교해 정렬한 다음 정렬된 부분을 합하는 방법.

그룹을 둘로 나누어서 재귀 호출한다는 방식은 병합 정렬과 비슷하지만 그룹을 나눌 때 미리 기준과 비교해서 나눈다는 점이 다르다.

1. 분할단계(divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽은 피벗보다 작은 요소들을 배치하고, 오른쪽은 피벗보다 큰 요소를 배치)로 분할한다.
2. 정복단계(Conquer): 부분 배열을 정렬한다. 배열 크기가 충분히 작지 않다면 재귀 호출을 이용해서 다시 분할 정복 방법 적용(재귀는 리스트가 1이하가 될 때까지 반복된다)
3. 결합단계(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

오른쪽 애니메이션에 파란 가로줄은 Pivot, 즉 기준이 되고 그 피벗을 기준으로 위아래를 나눈다.

 

 

 

핵심은 기준보다 작은 건 왼쪽으로 큰건 오른쪽으로 하는 재귀 함수로, 반복을 계속해서 나눈 리스트에서 기준을 정하고 피봇을 기준으로 나눈다는 것

 

 

알고리즘의 특징

---

장점

• 재귀가 호출될 때마다 최소한 하나의 기준(Pivot)은 최종적으로 위치가 정해져서 이 알고리즘이 반드시 끝난다는 것을 보장할 수 있음
• 퀵 소트라는 이름이 지어질 정도로 속도가 빠르다

단점

• 중복된 값이 있거나 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.

 

시간복잡도

---

평균적인 시간 복잡도를 빅오표기법으로 쓰면 O(n * logN) 인데, 불 필요한 데이터의 이동을 줄이고(피봇은 항상 고정되어 있음)먼 거리의 데이터를 교환하며, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 덕분에 같은 시간 복잡도를 가지는 다른 정렬 알고리즘과 비교했을 때에도 가장 빠르다는 것을 알 수 있다.

코드

---

 

# 퀵 정렬
# 리스트 a를 퀵 정렬로 정렬함
# 매게 변수로 어디서부터 어디까지 정렬할 건지 받음

#범위를 지정하여 정렬하는 재귀 호출 함수
def partition(a, start, end):
    #리스트가 한개 이하면 종료
    if end - start <= 0:
        return
    
    #기준값을 임의로 마지막 값으로 잡음 시작 값으로 잡아도 상관없음
    pivot = a[end] 
    i = start

    for j in range(start, end):
        if a[j] <= pivot:
           a[i], a[j] = a[j], a[i] #기준보다 작으면 왼쪽값과 교환하기
           i += 1
    a[i], a[end] = a[end], a[i]
    #재귀 호출 부분
    partition(a, start, i-1) #기준 값보다 작은 그룹들을 재귀 호출로 정렬
    partition(a, i+1, end) #기준 값보다 큰 그룹들을 재귀 호출로 정렬

#리스트 전체를 다시 재귀 호출로 부름
def quick_sort(a):
    partition(a, 0, len(a) - 1)

a = [5,6,2,9,1,3,4,7,8,32,16]
quick_sort(a)
print(a)