[알고리즘] 퀵 정렬

퀵 정렬 (quick sort)

• 기준점(pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성
• 각 왼쪽/오른쪽은 재귀용법을 사용해서, 다시 동일 함수를 호출하여 위 작업을 반복
• 함수는 왼쪽 / 기준점(pivot) / 오른쪽 을 리턴

코드

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]:
            left.append(data[index])
        else:
            right.append(data[index])
    
    return qsort(left) + [pivot] + qsort(right)

시간 복잡도

• O(n logn)
  * 길이(logn) X n (각 깊이마다 n번 검사)
• 최악의 경우 O(n^2)