퀵정렬이란?

퀵 정렬은 'quick'이라는 이름에서도 알 수 있듯이, 처리 속도가 빠른 정렬 알고리즘이다. 이 정렬은 대량의 데이터를 정렬할 때 자주 사용된다. 유명한 정렬 알고리즘 중에서도 실제로 사용되는 빈도가 높은 가장 중요한 알고리즘이기도 하다.

퀵 정렬은 '기준값을 선택한 후 그보다 작은 데이터 그룹과 큰 데이터 그룹으로 나눈다.'라는 처리를 반복 수행하여 데이터를 정렬하는 알고리즘이다.

퀵 정렬은 두 가지 처리로 이루어져 있다.

1. 기준값을 경계로 데이터를 대소로 나누는 처리
2. 나눈 데이터에 대해 반복적으로 똑같은 작업 실행하기

이와 같은 그림과 같이 퀵정렬을 실행할 수 있다.

코드 구현

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    lesser_arr, equal_arr, greater_arr = [], [], []
    for num in arr:
        if num < pivot:
            lesser_arr.append(num)
        elif num > pivot:
            greater_arr.append(num)
        else:
            equal_arr.append(num)
    return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)