https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

퀵정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까 ??

• 큰 숫자와 작은 숫자를 교환할 때 , 교환하기 위한 '기준' 을 바로 피벗이라고 표현한다.

• 분할 정복 알고리즘의 하나로 , 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다.

• 분할 정복 방법

  • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음 , 결과를 모아서 원래의 문제를 해결하는 전략이다.
  • 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.

array = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(array):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <=1:
        return array

    pivot = array[0] # 피벗은 첫 번째 원소
    tail  = array[1:] # 피벗을 제외한 리스트

    left_side = [x for x in tail if x<= pivot] # 분할된 왼쪽부분
    right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분

    #분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고 , 전체 리스트를 변환

    return quick_sort(left_side) +[pivot]+quick_sort(right_side)

print(quick_sort(array))