이제 start부터 right까지 이 과정을 반복하고 left부터 end까지도 이 과정을 반복합니다. 같은 알고리즘의 반복을 구현할 때는 재귀 함수를 이용합니다. 탈출 조건은 start가 end보다 크거나 같아지는 지점입니다. 바로 정렬하려는 데이터가 하나일 때까지 쪼개어(divide) 문제를 해결하는(conquer) 분할 정복 기법이지요.

코드 15-5 algorithm/algo_3/quick_sort.py ①

def quick_sort(data, start, end):
    # 탈출 조건
    if start >= end:
        return

    left = start
    right = end
    pivot = data[(start + end) // 2]

    # left와 right가 교차할 때까지 반복
    def quick_sort(data, start, end):
    while left <= right:
        # left 데이터가 pivot보다 크거나 같으면 멈춥니다
        while data[left] < pivot:
            left+=1
        # right 데이터가 pivot보다 작거나 같으면 멈춥니다
        while data[right] > pivot:
            right-=1

        # left와 right가 교차하지 않았다면 교환
        if left <= right:
            data[left], data[right] = data[right], data[left]
            left += 1
            right -= 1

    quick_sort(data, start, right)
    quick_sort(data, left, end)

자세한 설명은 주석을 넣어 두었습니다.