퀵 정렬 퀵 소트 quick sort

퀵 정렬(Quick Sort) 이해하기

728x90

퀵 정렬이란?

퀵 정렬은 분할 정복(Divide and Conquer) 기법을 활용한 효율적인 정렬 알고리즘입니다. 1959년 영국 컴퓨터 과학자 토니 호어(Tony Hoare)가 개발했습니다. 불안정 정렬에 속하며, 비교 기반의 정렬 알고리즘 중 하나입니다.

동작 원리

1. 피벗(Pivot) 선택: 정렬할 리스트에서 하나의 원소를 피벗으로 선택합니다. 일반적으로 리스트의 첫 번째 또는 마지막 원소를 피벗으로 사용합니다.
2. 파티셔닝(Partitioning): 피벗을 기준으로 리스트를 두 개의 부분 리스트로 분할합니다. 피벗보다 작은 값은 왼쪽 부분 리스트에, 큰 값은 오른쪽 부분 리스트에 배치합니다.
3. 재귀 호출(Recursive Call): 분할된 두 개의 부분 리스트에 대해 재귀적으로 퀵 정렬을 수행합니다. 부분 리스트의 크기가 충분히 작아질 때까지 이 과정을 반복합니다.
4. 합치기(Merge): 정렬된 두 개의 부분 리스트를 합쳐 전체 리스트를 정렬합니다.

반응형

시간 복잡도

• 평균 시간 복잡도: O(n log n)
  • 피벗이 적절히 선택되어 리스트를 균등하게 분할할 경우, 퀵 정렬은 평균적으로 O(n log n)의 시간 복잡도를 가집니다.
• 최악의 경우 시간 복잡도: O(n^2)
  • 리스트가 이미 정렬되어 있거나 역순으로 정렬되어 있는 경우에 발생합니다.
  • 이 경우, 파티셔닝 과정에서 한쪽 부분 리스트에 모든 원소가 포함되어 재귀 호출이 비효율적으로 진행됩니다.
• 공간 복잡도: O(log n)
  • 퀵 정렬은 주로 In-place 방식으로 구현되므로, 추가적인 메모리 공간을 필요로 하지 않습니다.
  • 단, 재귀 호출에 따른 스택 공간이 필요하므로 최악의 경우 O(log n)의 공간 복잡도를 가집니다.

장점

• 평균적으로 매우 빠른 정렬 속도를 보입니다.
• 메모리 사용량이 적어 공간 효율적입니다.
• 다양한 프로그래밍 언어에서 활용되고 있습니다.
• 정렬 과정에서 원소의 이동이 적어 캐시 효율성이 좋습니다.

단점

• 최악의 경우 시간 복잡도가 O(n^2)로 비효율적일 수 있습니다.
• 피벗 선택에 따라 성능이 크게 달라질 수 있습니다.
• 불안정 정렬이므로 동일한 값에 대한 순서가 바뀔 수 있습니다.
• 재귀 호출로 인해 스택 오버플로우 문제가 발생할 수 있습니다.

<Python 예제 코드>

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quicksort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quicksort(arr, low, pi - 1)
        quicksort(arr, pi + 1, high)

# Example usage
arr = [64, 34, 25, 12, 22, 11, 90]
n = len(arr)
quicksort(arr, 0, n - 1)
print("Sorted array is:")
for i in range(n):
    print("%d" % arr[i], end=" ")

 

<C++ 예제 코드>

#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quicksort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quicksort(arr, low, pi - 1);
        quicksort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    quicksort(arr, 0, n - 1);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

피벗 선택 전략

피벗 선택 전략은 퀵 정렬의 성능에 큰 영향을 미칩니다. 좋은 피벗을 선택하면 파티셔닝 과정에서 균등한 분할이 이루어져 효율적인 정렬이 가능합니다. 대표적인 피벗 선택 전략으로는 다음과 같은 것들이 있습니다.

• 첫 번째 원소를 피벗으로 선택하는 방법
• 마지막 원소를 피벗으로 선택하는 방법
• 무작위 원소를 피벗으로 선택하는 방법
• 중간값을 피벗으로 선택하는 방법 (Median-of-Three 파티셔닝)

활용 분야

• 데이터베이스 인덱싱
• 이미지 처리
• 통계 분석
• 대용량 데이터 처리
• 운영체제 작업 스케줄링
• численные методы

퀵 정렬은 분할 정복 기법을 사용하여 평균적으로 매우 빠른 정렬 속도를 보이는 알고리즘입니다. 효율적인 메모리 사용과 다양한 응용 분야로 인해 널리 사용되고 있습니다. 하지만 최악의 경우와 피벗 선택에 따라 성능이 크게 달라질 수 있으므로, 적절한 피벗 선택 전략을 사용하는 것이 중요합니다. 또한, 불안정 정렬이라는 단점이 있으므로, 안정성이 요구되는 경우에는 다른 정렬 알고리즘을 고려해야 합니다.

 

<Selection Sort, 선택 정렬>

https://tonnykang.tistory.com/182

선택정렬 Selection Sort