[알고리즘 개념정리] 퀵 정렬

• 선택 정렬보다 훨씬 빠른 정렬 알고리즘
• 분할 정복 전략

1. 기본단계 : 원소의 개수가 0이거나 1
2. 기준원소 : 배열에서 원소하나를 고른다.
3. 분할 : 모든 원소를 기준원소보다 작은 숫자로 이루어진 배열, 기준원소보다 큰 숫자들로 이루어진 배열로 나눈다.
4. 두 개의 하위 배열에 대해 재귀적으로 퀵 정렬을 호출하고 그 결과를 합치면 전체 배열이 정렬된다.

def quicksort(array):
    if len(array) < 2:
        return array # 기본단계
    else:
        pivot = array[0] # 기준원소
        # 분할
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)

def main():
    print(quicksort([3,5,2,1,4]))

if __name__ == "__main__":
    main()