[알고리즘 기초] 퀵 정렬 Quick Sort

QuickSort(퀵 정렬)는 배열 또는 리스트를 효율적으로 정렬하기 위해 분할 정복(Divide and Conquer) 방식을 사용하는 널리 사용되는 정렬 알고리즘입니다. 이 알고리즘은 배열에서 피벗(pivot) 요소를 선택하고, 다른 요소들을 피벗과 비교하여 두 개의 하위 배열로 분할하는 방식으로 동작합니다. 그런 다음 이 과정을 하위 배열에 대해 재귀적으로 반복하여 전체 배열이 정렬되도록 합니다.

퀵 정렬 알고리즘의 단계별 설명은 다음과 같습니다:

1. 피벗 선택: 배열에서 피벗으로 사용할 요소를 선택합니다. 피벗의 선택은 알고리즘의 성능에 영향을 미칩니다. 일반적인 방법으로는 첫 번째, 마지막 또는 중간 요소를 피벗으로 선택하거나, 임의의 요소를 사용하는 것입니다.

2. 분할: 배열의 요소들을 피벗을 기준으로 좌측과 우측의 두 개의 하위 배열로 재배치합니다. 피벗 자체는 정렬된 배열에서 올바른 위치에 위치하게 됩니다.

3. 재귀: 퀵 정렬 알고리즘을 좌측과 우측 하위 배열에 재귀적으로 적용합니다. 각 하위 배열에 대해 분할 단계를 반복합니다.

4. 결합: 정렬된 하위 배열들을 결합하여 최종적으로 정렬된 배열을 형성합니다.

퀵 정렬의 평균 시간 복잡도는 일반적으로 O(n log n)으로, 큰 데이터셋에 대해 가장 빠른 정렬 알고리즘 중 하나입니다. 그러나, 최악의 경우에는 피벗의 선택이 불균형하게 이루어지고 이미 정렬되어 있는 또는 거의 정렬된 배열의 경우에는 시간 복잡도가 O(n^2)로 감소할 수 있습니다.

다음은 퀵 정렬 알고리즘의 Python 구현 예시입니다.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)

# Example usage:
unsorted_list = [64, 34, 25, 12, 22, 11, 90]
sorted_list = quick_sort(unsorted_list)
print("Sorted array:", sorted_list)

위 코드를 응용해서, 오름차순/내림차순으로 정렬해주는 함수를 아래와 같이 만들 수 있습니다.

def qSort(ns, asc=True):
    if len(ns) < 2:
        return ns

    pivotVal = ns[len(ns) // 2]

    leftNums = [x for x in ns if x < pivotVal]
    sameNums = [y for y in ns if y == pivotVal]
    rightNums = [z for z in ns if z > pivotVal]

    if asc:
        return qSort(leftNums, asc=asc) + sameNums + qSort(rightNums, asc=asc)
    else:   # 출력 순서 거꾸로 바꿔주기
        return qSort(rightNums, asc=asc) + sameNums + qSort(leftNums, asc=asc)