100년 뒤 개발자 한승규입니다.

오늘부터 분할정복 복습에 들어가는데.... 시간이 없어서 간단하게 분할정복의 대장님이신 퀵 정렬만 보려고 한다.

분할 정복은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제의 답을 재귀 호출로 계산하고, 다시 각 부분 문제의 답으로 전체 문제의 답을 계산하는 것이다.

퀵 정렬에서는 피벗을 기준으로 피벗보다 더 작은 값들의 리스트, 피벗보다 더 큰 값들의 리스트로 분할 한 후, 재귀 호출로 길이가 1이하 가 될 때까지 나누어주고 다시 묶어주는 방식으로 빠르게 정렬해준다.

def quick_sort(data):
    # 데이터의 길이가 1이라면 더이상 정렬할 필요가 없다.
    if len(data) <= 1:
        return data

    pivot = data[0]
    left_data = []
    right_data = []

    for i in data[1:]:
        if i >= pivot:
            right_data.append(i)
        else:
            left_data.append(i)
	
    # 각각 정렬된 값들을 다시 붙이기
    return quick_sort(left_data) + [pivot] + quick_sort(right_data)

오늘은 이만...ㅠㅠ

피곤은 하고... 그렇다고 알고리즘 빼먹을 수는 없어서 이거라도 올립니다!