퀵 정렬 (Quick Sort)

퀵 정렬은 분할 정복(Divide and Conquer) 방식을 이용하여 정렬하는 알고리즘 중 하나입니다.

참조 블로그 퀵 정렬

• 알고리즘 간단한 설명

퀵 정렬의 기본 아이디어는 ‘피벗(Pivot)’ 이라 불리는 하나의 원소를 기준으로 리스트를 두 개의 부분 리스트로 나누고, 각 부분 리스트를 재귀적으로 퀵 정렬을 적용하는 것입니다. 일반적으로 피벗은 리스트의 가자 왼쪽이나 오른쪽, 또는 중간에 위치한 값을 사용합니다.

퀵 정렬의 과정은 다음과 같습니다.

• 알고리즘 상세 설명

리스트에서 하나의 원소를 선택하여 피벗으로 지정합니다. 피벗을 기준으로 리스트를 두 개의 부분 리스트로 나눕니다. 이 때, 피벗보다 작은 원소는 왼쪽 리스트에, 큰 원소는 오른쪽 리스트에 위치하도록 합니다. 해당 부분 리스트는 이미 정렬되었다고 가정합니다. 각 재귀 호출이 종료되면, 피벗을 기준으로 분할된 부분 리스트들을 병합하여 전체 리스트를 정렬합니다. 퀵 정렬은 일반적으로 평균적인 경우에는 매우 빠른 속도로 정렬을 수행합니다.

• 시간복잡도

퀵 정렬의 시간 복잡도는 평균적으로 O(n log n)이며, 최악의 경우 O(n^2)이 됩니다. 이는 리스트를 분할할 때 피벗을 어떻게 선택하느냐에 따라 달라지는데, 만약 리스트가 이미 정렬되어 있는 경우나 역순으로 정렬되어 있는 경우 등에서 피벗을 가장 작거나 큰 값으로 선택하는 경우 최악의 시간 복잡도가 발생합니다. 이러한 경우를 방지하기 위해서는 피벗을 무작위로 선택하거나, 리스트의 중간값 등을 피벗으로 선택하는 방법이 있습니다.

• 주의 및 단점

최악의 경우(이미 정렬되어 있는 리스트 등)에는 불균형한 분할이 발생하여 시간 복잡도가 O(n^2)까지 증가할 수 있습니다. 이러한 문제를 방지하기 위해, 피벗을 선택하는 방법을 무작위로 선택하거나, 중간값 등을 선택하여 최악의 경우 시간 복잡도를 개선할 수 있습니다.

퀵 정렬은 분할 정복 알고리즘 중 하나이므로, 재귀적인 호출을 사용합니다. 이 때, 스택 자료구조를 사용하여 재귀 호출을 구현하면 스택 오버플로우 문제가 발생합니다. 따라서, 퀵 정렬은 최악의 경우 O(n)의 추가적인 메모리를 사용하여 스택 오버플로우 문제를 해결합니다. 이를 위해, 퀵 정렬의 재귀 호출을 수행할 때는 작은 부분 리스트부터 처리하여 메모리 사용량을 최소화하며, 재귀 호출 대신 반복문을 사용하는 방법도 있습니다.

퀵 정렬은 일반적으로 빠른 속도로 정렬을 수행하며, 안정성을 보장하지는 않습니다.
따라서, 리스트의 크기가 작은 경우나 정렬된 리스트를 정렬할 때는 다른 알고리즘을 사용하는 것이 더욱 효율적일 수 있습니다.

def quick_sort(arr):
    # 리스트 길이가 1 이하인 경우, 즉 이미 정렬되어 있는 경우나 원소가 하나인 경우는 정렬이 된 것으로 간주하고 바로 반환합니다.
    if len(arr) <= 1:
        return arr
    
    # 그렇지 않는 경우, 피벗으로 리스트의 중간값을 선택합니다.    
    pivot = arr[len(arr)//2]
    
    # 이를 기준으로 리스트를 세 부분으로 분할합니다.
    left, right, equal = [],[],[]
    
    # 분할된 각 부분 리스트에 대해서 재귀적으로 퀵 정렬을 수행합니다.
    for i in arr:
        if i < pivot:
            left.append(i)
        elif i > pivot:
            right.append(i)
        else:
            equal.append(i)
            
    # 분할된 부분 리스트들을 병합하여 정렬된 리스트를 반환합니다.
    return quick_sort(left) + equal + quick_sort(right)

arr = [3,2,4,27,5,1,6,22,15]

print(quick_sort(arr))

[1, 2, 3, 4, 5, 6, 15, 22, 27]