[알고리즘] 퀵 정렬(Quick Sort) (Python)

1. 기본 원리

• 기준점(pivot) 기준으로 기준점보다 작은 데이터는 왼쪽으로, 기준점보다 큰 데이터는 오른쪽으로 보내는 함수 작성
• 보통 기준점(pivot)은 범위에서 맨 앞에 있는 것으로 선택
• 기준점(pivot) 왼쪽과 오른쪽 범위를 재귀 함수로 다시 정렬해주는 프로세스 반복
• 모든 데이터가 [기준점(pivot), 왼쪽, 오른쪽] 쌍으로 분리가 될 때까지 반복
• 분리되어 각각의 범위가 정렬된 것들을 다시 병합

 

2. 코드 구현 전 생각정리

• 3 5 1 7 4  (3이 기준점)
• 1 3 5 7 4  (5가 기준점)
• 1 3 4 5 7
• Python list를 활용해서 재귀함수를 통해 정렬된 list를 이어나가면 어떨까?

 

3. 코드 구현

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

 

4. 시간 복잡도

일반적일 때: O(nlogn) -> 단계가 logn만큼 생성, 각 단계별로 n만큼 비교하는 과정

최악일 때: O(n^2) -> 모든 데이터를 분석해야 할 때 ex) 1 2 3 4 5