퀵 정렬 (Quick Sort) 총 정리 - 개념, 원리, 동작 예시, 시간 복잡도, C언어, Java, Python 예시코드, 주의점, 장단점

퀵 정렬(Quick Sort)

 

 

 

1. 퀵 정렬이란?

퀵 정렬은 "분할 정복(Divide and Conquer)" 기법을 활용한 정렬 알고리즘입니다. 기준이 되는 피벗(Pivot)을 설정하고, 이를 기준으로 작은 값과 큰 값을 분리한 뒤 재귀적으로 정렬합니다. 평균적으로 매우 빠르며, 효율적인 정렬 알고리즘 중 하나로 평가받습니다.

---

 

 

2. 원리

1. 피벗을 선택합니다.
2. 피벗을 기준으로 배열을 나누어, 피벗보다 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 이동시킵니다.
3. 왼쪽과 오른쪽 부분 배열에 대해 재귀적으로 정렬을 수행합니다.
4. 모든 재귀 호출이 끝나면 정렬이 완료됩니다.

---

 

 

3. 동작 예시 (구체적인 설명)

정렬할 배열: [10, 80, 30, 90, 40, 50, 70]

피벗은 항상 배열의 마지막 원소로 선택.

1. 첫 번째 분할:
   • 피벗: 70
   • 배열 분할: [10, 30, 40, 50] (작음) + [70] (피벗) + [80, 90] (큼)
2. 왼쪽 부분 배열 [10, 30, 40, 50] 정렬:
   • 피벗: 50
   • 분할: [10, 30, 40] + [50]
3. 오른쪽 부분 배열 [80, 90] 정렬:
   • 피벗: 90
   • 분할: [80] + [90]
4. 정렬 완료:
   • 병합: [10, 30, 40, 50, 70, 80, 90]

---

 

 

4. 시간 복잡도

• 최선의 경우: O(n log n) (피벗이 배열을 균등하게 나눌 때)
• 평균적인 경우: O(n log n)
• 최악의 경우: O(n²) (피벗이 배열의 최댓값 또는 최솟값일 때)

---

 

 

5. 코드 예제

C 코드

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j < high; 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[] = {10, 80, 30, 90, 40, 50, 70};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

 

Java 코드

public class QuickSort {

    public static 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);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 80, 30, 90, 40, 50, 70};

        quickSort(arr, 0, arr.length - 1);

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

 

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)

arr = [10, 80, 30, 90, 40, 50, 70]
print(quick_sort(arr))

---

 

 

6. 주의점

1. 피벗 선택이 중요합니다. 최적의 성능을 위해 중앙값을 선택하거나 랜덤 피벗 방식을 사용하는 것이 유리합니다.
2. 최악의 경우를 방지하기 위해 입력 데이터를 사전 처리할 수도 있습니다.

---

 

 

7. 장단점

장점

• 평균 시간 복잡도가 O(n log n)으로 빠름.
• 추가 메모리 사용이 적음 (인플레이스 정렬 가능).

단점

• 최악의 경우 시간 복잡도가 O(n²).
• 재귀 호출이 많아 스택 오버플로우 가능성 있음.

 

 

함께 보면 좋은 글

코딩 테스트에 나오는 거의 모든 정렬 알고리즘들에 대해 비교했습니다. 언제 어떤 정렬 알고리즘을 쓰면 좋은지에 대해서도 작성했습니다. 아래 링크에 자세히 작성했습니다.

 

2025.01.03 - [알고리즘] - 정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주요 특징, 상황에 따른 선택 기준

정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주