[알고리즘] 퀵 정렬이란? (개념, 파이썬 코드)

퀵 정렬(Quick Sort)이란?

분할 정복 (Divide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘

*분할 정복 이란?

문제를 작게 분할한 후 각각을 해결하고, 그 결과를 이용해 전체 문제를 해결하는 알고리즘

• 방법
  • 피봇(pivot)이라는 값을 하나 정한다. (임의로 정할 수 있지만, 여기서는 중간에 있는 값을 하나 정해보자.)
  • 피봇보다 작은 값을 left 배열에, 피봇보다 큰 값을 right 배열에 추가한다.
  • left(피봇보다 작은 값들), 피봇, right(피봇보다 큰 값들) 로 만들어진다.
  • left, right 배열에 대해 위 작업을 재귀적으로 반복한다.

 

파이썬으로 구현하기

방법1

• pivot 보다 작은 값을 왼쪽 배열에, 큰 값을 오른쪽 배열에 추가한다.
• 각 배열에 대해 위 작업을 반복한다.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    n = len(arr)
    pivot = n // 2  # pivot 위치를 결정한다.

    left, right = [], []  # left : pivot 보다 작은 원소, right : pivot보다 큰 원소
    for i in range(n):
        if i != pivot:
            if arr[i] <= arr[pivot]:
                left.append(arr[i])
            else:
                right.append(arr[i])

    return quick_sort(left) + [arr[pivot]] + quick_sort(right)


if __name__ == "__main__":
    arr = [1,6,4,2,3,5]

    print(f"before : {arr}")  # 정렬 전 리스트
    sorted_arr = quick_sort(arr)
    print(f"after : {sorted_arr}")  # 정렬 후 리스트

 

방법2

(방법1) 처럼 구현해도 되지만, left와 right 배열을 별도로 사용하므로 메모리가 더 소요된다.

이 방법은 배열 안에서 스왑 하여 정렬하는 방법이다.

def quick_sort(arr, low, high):
    if low >= high:
        return
    
    mid = partition(arr, low, high)

    quick_sort(arr, low, mid-1)
    quick_sort(arr, mid, high)

def partition(arr, low, high):
    pivot = arr[(low + high) // 2]

    while low <= high:
        while arr[low] < pivot:  # 피봇보다 큰 값이 나타날 때까지 인덱스를 증가시킨다.
            low += 1
        while arr[high] > pivot:  # 피봇보다 작은 값이 나타날 때까지 인덱스를 감소시킨다.
            high -= 1
        if low <= high:  # low와 high가 아직 교차하지 않았다면, arr[low]는 피봇보다 큰 값, arr[high]는 피봇보다 작은 값이므로 서로 교환한다.
            arr[low], arr[high] = arr[high], arr[low]
            low, high = low + 1, high - 1

    return low


if __name__ == "__main__":
    arr = [1,6,4,2,3,5]

    print(f"before : {arr}")  # 정렬 전 리스트
    quick_sort(arr, 0, len(arr)-1)
    print(f"after : {arr}")  # 정렬 후 리스트

 

시간 복잡도

입력 데이터의 크기가 N일 때,

두 개의 배열로 분할하여 문제를 풀어나가기 때문에

시간 복잡도는 평균적으로 O(n log n)이다.

 

하지만 최악의 경우, O(n^2)이 소요된다.

배열이 오름차순 또는 내림차순으로 정렬되어 있는 경우

왼쪽, 오른쪽 배열이 균등하게 분할되지 않고 ex. 왼쪽은 1개, 오른쪽은 나머지 값들로 계속 분할되게 되면

각각의 작업당 n번, n-1번, n-2번, ... , 1번을 모두 확인해야 하기 때문이다.