[Python] 정렬 / 퀵 정렬(Quick Sort)

퀵 정렬

• 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와 비교하며 정렬하는 비교정렬입니다.
• 평균적으로 매우 빠른 속도로 정렬을 수행합니다.
• 분할 정복 방법을 수행합니다.
• 분할 정복 방법이란, 각각 두개의 문제로 분리하여 해결한 다음 결과를 모아서 원래의 문제를 해결합니다.

퀵 정렬 수행 방법

• 임의의 하나의 원소를 선택합니다.(선택된 원소의 위치를 pivot이라 하고, 보통 맨 처음을 pivot으로 지정)
• pivot보다 작은 원소들을 왼쪽, pivot보다 큰 원소들을 오른쪽으로 배치합니다.
• pivot을 기준으로 분할하여 순환 호출을 통해 반복 정렬을 하며 마칩니다.

 

퀵 정렬 코드

def quick_sort(seq, start, end):            # 배열의 시작과 끝점을 입력
    if start >= end:     # 원소가 1개인 경우 return
        return
    pivot = start        # 피벗은 첫번째 원소
    left, right = start + 1, end

    # left와 right가 엇갈린 경우 반복 종료
    while left <= right:
        while left <= end and seq[left] <= seq[pivot]:    # 범위 내에서 left가 피벗보다 클 경우 찾기
            left += 1
        while right > start and seq[right] >= seq[pivot]: # 범위 내에서 right가 피벗보다 작을 경우 찾기
            right -= 1
        # 엇갈린 경우 > right와 피벗 위치 바꿔주기, 피벗의 위치가 정해진다. 반복 종료
        if left > right:
            seq[pivot], seq[right] = seq[right], seq[pivot]
        # 엇갈리지 않았다면 left와 right 위치를 바꿔주기
        else:
            seq[left], seq[right] = seq[right], seq[left]

    print(seq)
    quick_sort(seq, start, right - 1)    # right는 자리를 찾은 pivot -> pivot - 1, pivot + 1
    quick_sort(seq, right + 1, end)

퀵 정렬 수행 과정

• 맨 앞의 원소를 pivot으로 지정합니다.
• pivot을 제외한 배열에서 left는 pivot보다 작은 값들이 나올동안 오른쪽으로 스캔, right는 pivot보다 큰 값들이 나올동안 왼쪽으로 스캔합니다.
• left에서 pivot보다 큰 값을, right에서 pivot보다 작은 값을 찾은 경우 서로 swap합니다.
• 단, 여기서 left와 right가 엇갈린 경우에는 스캔이 끝났고 pivot의 자리를 찾았으므로 pivot과 right의 값을 swap합니다.
• pivot 기준으로 남은 왼쪽, 오른쪽에서 순환 호출을 통해 퀵 정렬을 반복합니다.