퀵정렬 알고리즘 (Quick Sort) - 파이썬 예제

퀵 정렬 원리

퀵정렬은 효율적인 정렬 알고리즘 중 하나로, 다음과 같은 기본 아이디어에 기반하여 동작합니다:

1. 피벗 선택: 배열에서 하나의 요소를 선택합니다. 이 요소를 피벗이라고 합니다.
2. 분할: 배열을 두 개의 부분 배열로 분할합니다. 첫 번째 부분 배열에는 피벗보다 작은 모든 요소가 포함되며, 두 번째 부분 배열에는 피벗보다 큰 모든 요소가 포함됩니다.
3. 재귀적 정렬: 두 부분 배열을 재귀적으로 정렬합니다.

---

퀵정렬의 원리와 동작 방식에 대해 좀 더 상세하게 설명하겠습니다.

---

1. 피벗 선택

   • 피벗(pivot)은 정렬될 배열에서 선택된 특정 요소를 말합니다.
   • 선택된 피벗을 기준으로 배열이 두 부분으로 분할됩니다.
   • 피벗의 선택 방법은 다양하다. 첫 번째 요소, 마지막 요소, 중간 요소, 무작위 요소 또는 다른 통계적 방법을 사용할 수 있습니다. 선택된 피벗에 따라 퀵정렬의 성능이 달라질 수 있습니다. 아래 예제 코드에선 첫 번째 요소를 피벗으로 선택하였습니다.

2. 분할

   • 이 단계에서 배열은 두 부분 배열로 분할됩니다 : 피벗보다 작은 요소들의 부분 배열과 피벗보다 큰 요소들의 부분 배열.
   • 이 분할은 left와 right라는 두 개의 포인터를 사용하여 수행됩니다. left 포인터는 배열의 왼쪽에서 오른쪽으로 이동하면서 피벗보다 큰 요소를 찾고, right 포인터는 배열의 오른쪽에서 왼쪽으로 이동하면서 피벗보다 작은 요소를 찾습니다. 두 포인터가 교차할 때까지 이 과정이 반복됩니다.
   • 피벗을 올바른 위치(피벗의 왼쪽에는 피벗보다 작은 요소들, 오른쪽에는 큰 요소들)로 이동시키기 위해 피벗과 right 포인터가 가리키는 요소를 교환합니다.

3. 재귀적 정렬

   • 분할 단계를 통해 피벗을 기준으로 생성된 두 부분 배열이 생성됩니다.(피벗의 왼쪽에는 피벗보다 작은 요소들, 오른쪽에는 큰 요소들)
   • 이 두 부분 배열에 대해 퀵정렬 알고리즘을 재귀적으로 적용하여 정렬합니다. 이 때, 각 부분 배열에 대해 새로운 피벗이 선택되고 위의 과정이 반복됩니다.

---

퀵정렬은 최선의 경우, 평균의 경우 O(n log n)의 시간 복잡도를 가지지만 최악의 경우 O(n^2)의 시간 복잡도를 가질 수 있습니다. 평균적으로 선택정렬, 삽입정렬, 버블정렬에 비해 빠른 속도를 보여줍니다.

---

퀵 정렬 - 파이썬 코드 설명

위에서 설명한 퀵 정렬 알고리즘을 파이썬 코드를 통해 살펴 보겠습니다. 다음 예제는 '제로베이스 데이터스쿨' 강의를 참고하였습니다.

def quick_sort(lst, start, end, reverse=False):
    if start >= end:
        return
    pivot = start
    left = start + 1
    right = end

    while left <= right:
        while (not reverse and (left <= end) and (lst[left] <= lst[pivot])) or\
                (reverse and (left <= end) and (lst[left] >= lst[pivot])):
            left += 1
        while (not reverse and (right > start) and (lst[right] >= lst[pivot])) or\
                (reverse and (right > start) and (lst[right] <= lst[pivot])):
            right -= 1
        if left > right:
            lst[right], lst[pivot] = lst[pivot], lst[right]
        else:
            lst[left], lst[right] = lst[right], lst[left]

    quick_sort(lst, start, right - 1, reverse)
    quick_sort(lst, right + 1, end, reverse)

• quick_sort 함수는 퀵정렬을 수행하는 주요 함수입니다. 이 함수는 재귀적으로 호출되어 정렬을 수행합니다.

퀵정렬 함수 정의:

def quick_sort(lst, start, end, reverse=False):

• quick_sort는 퀵정렬 알고리즘을 구현한 함수입니다.
• lst는 정렬할 리스트, start는 시작 인덱스, end는 마지막 인덱스입니다.
• reverse는 선택적 매개변수로, 기본적으로 False로 설정되어 있습니다. 이는 정렬 방향을 결정하는데 사용됩니다.

재귀의 종료 조건:

    if start >= end:
        return

• start가 end보다 크거나 같으면 더 이상 정렬할 요소가 없으므로 함수를 종료합니다.

포인터 초기화 및 분할 과정:

    pivot = start
    left = start + 1
    right = end

• 피벗은 start 인덱스의 요소로 설정됩니다. (이 코드에서는 항상 첫 번째 요소가 피벗으로 선택됩니다.)
• left 포인터는 피벗 바로 다음 요소부터 시작하고, right 포인터는 리스트의 마지막 요소에서 시작합니다.

분할 과정:

    while left <= right:

• left 포인터와 right 포인터가 교차하기 전까지 반복합니다.

피벗과의 비교 및 포인터 이동:

while (not reverse and (left <= end) and (lst[left] <= lst[pivot])) or\
                (reverse and (left <= end) and (lst[left] >= lst[pivot])):
            left += 1
        while (not reverse and (right > start) and (lst[right] >= lst[pivot])) or\
                (reverse and (right > start) and (lst[right] <= lst[pivot])):
            right -= 1

• left 포인터는 피벗보다 큰 요소를 찾을 때까지 오른쪽으로 이동합니다.
• right 포인터는 피벗보다 작은 요소를 찾을 때까지 왼쪽으로 이동합니다.

포인터의 위치에 따른 분할 및 교환:

        if left > right:
            lst[right], lst[pivot] = lst[pivot], lst[right]
        else:
            lst[left], lst[right] = lst[right], lst[left]

• 만약 left 포인터가 right 포인터보다 오른쪽에 위치한다면, 피벗과 right 포인터 위치의 요소를 교환합니다.
• 그렇지 않으면, left와 right 포인터 위치의 요소를 교환합니다.

재귀적 호출:

	quick_sort(lst, start, right - 1, reverse)
    quick_sort(lst, right + 1, end, reverse)

• 피벗을 기준으로 나눈 두 부분 배열에 대해 퀵정렬 알고리즘을 재귀적으로 적용합니다.

정방향 및 역방향 정렬:

• reverse 매개변수를 사용하여 오름차순(정방향) 또는 내림차순(역방향)으로 정렬할 수 있습니다.
• 코드 내부에서 reverse의 값에 따라 비교 연산자가 바뀌어 적절한 방향으로 정렬을 수행합니다.

---

quick_sort 함수는 피벗을 기준으로 배열을 분할하고, 분할된 각 부분 배열에 대해 재귀적으로 같은 알고리즘을 적용함으로써 전체 배열을 정렬하는 방식으로 동작합니다.