퀵정렬 (Quick sort)

퀵정렬

• 기준점(pivot이라고 부름)을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성한다.
• 왼쪽 오른쪽으로 나눈 데이터들을 동일한 함수를 호출하여 나누는 작업을 반복한다.
• 작 작업을 통해 리턴받은 데이터를 결합하면 정렬된 데이터를 얻을 수 있다.

구현

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


if __name__ == "__main__":
    result = qsort([4, 7, 134, 53, 12, 678, 432, 1, 8])
    print(result)