퀵 정렬

• 퀵 정렬은 분할 정복 (Devide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘이다.
• 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
• pivot 값을 array의 첫 번째 요소로 잡기 때문에 만약 데이터가 이미 정렬 된 경우라면 시간 복잡도가 O(N^2)까지 늘어날 수 있습니다.

퀵 정렬 알고리즘 기본 개념

• 하나의 리스트를 피벗을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
• 퀵 정렬은 3단계로 이루어져있다.

1. 분할(Divide) : 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽 = 피벗보다 작은 요소들, 오른쪽 = 피벗보다 큰 요소들)로 분할한다.
2. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
3. 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.

• 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

퀵 정렬 알고리즘 로직

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot - 기준점을 의미하기 떄문에 다르게 불러도 된다. 다만 피벗이라 많이 칭함)이라고 한다.
2. 피벗 앞에는 피봇보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

퀵 정렬의 구현 코드

• 퀵 정렬의 기본적인 구현 코드를 통해서 더 자세하게 알아보자

# 가장 일반적인 퀵 정렬
def quick_sort(array, start, end):
    if start >= end: return  # 원소가 1개인 경우
    pivot = start  # 피벗은 첫 요소
    left, right = start + 1, end #left와 right의 인덱스

    while left <= right:
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]:
            right -= 1
        if left > right:  # 엇갈린 경우
            array[right], array[pivot] = array[pivot], array[right]
        else:  # 엇갈리지 않은 경우
            array[right], array[left] = array[left], array[right]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

• 위는 대표적인 퀵 정렬 알고리즘의 구현 코드이다.
• 메소드의 매개변수를 array, 정렬할 배열 부분의 시작점, 정렬할 배열 부분의 끝점을 받아서 사용한다.