5. 퀵정렬(Quick sort)

1. 분할 정복(Divide and Conquer)
* 문제를 여러 개의 독립적인 하위 문제로 나눠서 각각 해결한 후, 그 결과를 합쳐서 원래 문제를 해결하는 방식
* 재귀적으로 하위 문제를 풀고, 합병 과정을 거치는 게 특징

2. 분할 정복을 사용하는 대표적인 정렬: 퀵 정렬
* 정렬 알고리즘의 꽃
* 기준점(pivot)을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성
* 왼쪽, 오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함

2-1. 퀵 정렬 알고리즘 구현하기
* 만약 리스트 갯수가 한 개이면 해당 리스트를 반환
* 그렇지 않으면, 리스트 맨 앞의 데이터를 기준점(pivot)으로 설정
* left, right 리스트 변수를 만듦
* 맨 앞의 데이터를 뺀 나머지 데이터를 기준점과 비교
    * 기준점보다 작으면 left.append
    * 기준점보다 크면 right.append
* return quicksort(left) + pivot + quicksort(right)로 재귀 호출


def quicksort(data):
    if len(data) <= 1:
        return data

    pivot = data[0]
    left, right = list(), list()

    for index in range(1, len(data)):
        if pivot > data[index]:
            left.append(data[index])
        else:
            right.append(data[index])
    return quicksort(left) + [pivot] + quicksort(right)
    
import random

data_list = random.sample(range(100), 10)
print(data_list)
print(quicksort(data_list))
-->
[92, 88, 23, 69, 2, 51, 20, 68, 55, 73]
[2, 20, 23, 51, 55, 68, 69, 73, 88, 92]


2-2. 위 퀵정렬 코드를 list comprehension을 사용하여 더 좋은 알고리즘으로 작성해보기
def quicksort(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 quicksort(left) + [pivot] + quicksort(right)


data_list = random.sample(range(100), 10)
print(data_list)
print(quicksort(data_list))
-->
[52, 34, 15, 31, 49, 36, 99, 57, 23, 68]
[15, 23, 31, 34, 36, 49, 52, 57, 68, 99]