[코딩 + 알고리즘 완주반] 18일차. 퀵 정렬

# 퀵 정렬

기준점을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수 작성

각 왼쪽, 오른쪽은 재귀 용법을 사용해서 반복 

return qsort(left) + [pivot] + qsort(right)

 

#퀵 정렬 구현

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)

# 리스트 컴프리헨션 사용

def qsort(data):
    if len(data) <= 1:
        return data
    
    pivot = data[0]

    left = [ item for item in data[1:] if pivot > item ]
    right = [ item for item in data[1:] if pivot <= item ]
    
    return qsort(left) + [pivot] + qsort(right)

# 시간 복잡도

병합정렬과 유사 , 시간복잡도는 O(nlogn)

최악의 경우 모든 데이터를 비교 - O(n^2)