분할 알고리즘과 퀵정렬

퀵정렬(Quick sorting) 알고리즘 

분할 알고리즘으로 분할된 부분 배열을 재귀적으로 정렬하는 알고리즘

 

분할(partition) 알고리즘

분할 원소(partition element 혹은 pivot item)보다 작은 원소는 왼쪽 배열로, 큰 원소는 오른쪽 배열로 분할하는 알고리즘

def partition(a, low, high):
    pivot = a[low]             # 배열의 첫 요소를 pivot으로 설정
    i = low + 1                # 왼쪽 포인터는 pivot 다음 위치에서 시작
    j = high                   # 오른쪽 포인터는 배열의 끝에서 시작

    while 1:
        while i <= high and a[i] < pivot:
            i += 1             # 왼쪽에서 pivot보다 크거나 같은 값 찾기
        while j >= low + 1 and a[j] > pivot:
            j -= 1             # 오른쪽에서 pivot보다 작거나 같은 값 찾기

        if i > j:
            break              # 포인터가 엇갈리면 반복 종료

        a[i], a[j] = a[j], a[i]  # 찾은 두 값을 서로 교환 (잘못된 위치의 값 교환)

    a[low], a[j] = a[j], a[low]  # pivot을 자신의 올바른 위치(j)로 이동
    return j                     # pivot의 최종 위치 반환 (분할 기준점)

 

퀵정렬

def quickSort(a, low, high):
    if low >= high:
        return
    k = partition(a, low, high)

    quickSort(a, low, k - 1)
    quickSort(a, k + 1, high)