퀵 정렬

퀵 정렬 (Quick Sort)

분할 정복(divide and conquer) 방식을 사용하는 정렬 알고리즘으로, 피벗(pivot)을 기준으로 배열을 분할하고 재귀적으로 정렬하는 방식입니다.

핵심 요소

핵심 요소	설명
피벗(Pivot)	배열을 분할하는 기준이 되는 원소로, 일반적으로 배열의 마지막 요소를 선택
분할(Partition)	피벗을 기준으로 배열을 작은 값과 큰 값으로 나누는 과정
재귀(Recursion)	분할된 부분 배열에 대해 동일한 정렬 과정을 반복적으로 수행하는 방식

시간 복잡도

최선의 경우	O(n log n)
평균의 경우	O(n log n)
최악의 경우	O(n²)

주요 특징

•

불안정 정렬: 동일한 값의 원소들의 상대적 위치가 변경될 수 있음

•

제자리 정렬: 추가적인 메모리 공간이 거의 필요하지 않음

•

다른 정렬 알고리즘에 비해 일반적으로 빠른 성능을 보임

예시 코드 (Java)

/**
 * 퀵 정렬(Quick Sort)은 분할 정복 알고리즘의 하나로, 평균적으로 O(n log n)의 시간 복잡도를 가지는 효율적인 정렬 알고리즘입니다.
 * 
 * 알고리즘 순서도:
 * 1. 피벗(Pivot)을 선택합니다. (일반적으로 배열의 마지막 요소를 선택)
 * 2. 배열을 피벗을 기준으로 두 부분으로 나눕니다. (피벗보다 작은 값과 큰 값으로 분할)
 * 3. 분할된 두 부분 배열에 대해 재귀적으로 퀵 정렬을 수행합니다.
 * 4. 모든 부분 배열이 정렬되면 전체 배열이 정렬됩니다.
 * 
 * 특징:
 * - 평균 시간 복잡도: O(n log n)
 * - 최악 시간 복잡도: O(n^2) (이미 정렬된 배열에서 피벗 선택이 비효율적일 경우)
 * - 공간 복잡도: O(log n) (재귀 호출 스택 사용)
 * - 제자리 정렬(In-place Sort)로 추가 메모리 사용이 적음
 */
public class QuickSort {

    /**
     * 배열을 퀵 정렬하는 메소드.
     *
     * @param arr 정렬할 배열
     * @param low 정렬할 부분 배열의 시작 인덱스
     * @param high 정렬할 부분 배열의 끝 인덱스
     */
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1); // 왼쪽 부분 정렬
            quickSort(arr, pivotIndex + 1, high); // 오른쪽 부분 정렬
        }
    }

    /**
     * 배열을 분할하고 피벗의 최종 위치를 반환하는 메소드.
     *
     * @param arr 분할할 배열
     * @param low 분할할 부분 배열의 시작 인덱스
     * @param high 분할할 부분 배열의 끝 인덱스
     * @return 피벗의 최종 위치 인덱스
     */
    private 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; // 피벗의 인덱스 반환
    }

    /**
     * 메인 메소드. 배열을 정렬하고 결과를 출력.
     *
     * @param args 실행 시 전달되는 명령행 인자
     */
    public static void main(String[] args) {
        int[] data = {10, 7, 8, 9, 1, 5};
        System.out.println("Unsorted array:");
        for (int num : data) {
            System.out.print(num + " ");
        }

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

        System.out.println("\nSorted array:");
        for (int num : data) {
            System.out.print(num + " ");
        }
    }
}
Java
복사

Java Collections로 구현

import java.util.ArrayList;
import java.util.Collections;

public class QuickSortCollection {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(64);
        list.add(34);
        list.add(25);
        list.add(12);
        list.add(22);
        
        System.out.println("정렬 전: " + list);
        Collections.sort(list);  // 퀵 정렬 기반의 정렬 수행
        System.out.println("정렬 후: " + list);
    }
}
Java
복사

퀵 정렬 vs 병합 정렬

비교 기준	퀵 정렬	병합 정렬
시간 복잡도 (평균)	O(n log n)	O(n log n)
시간 복잡도 (최악)	O(n²)	O(n log n)
공간 복잡도	O(log n)	O(n)
안정성	불안정 정렬	안정 정렬
제자리 정렬	예	아니오

퀵 정렬 & 병합 정렬 공통점

•

분할 정복(Divide and Conquer) 알고리즘을 사용

•

평균 시간 복잡도가 O(n log n)으로 동일

•

재귀적 방식으로 구현 가능

•

대규모 데이터 처리에 효율적

•

비교 기반 정렬 알고리즘

주요 차이점 설명

비교 항목	퀵 정렬	병합 정렬
메모리 사용	추가 메모리 거의 불필요	배열 크기만큼의 추가 메모리 필요
안정성	불안정 정렬 (순서 유지 안됨)	안정 정렬 (순서 유지됨)
실제 성능	일반적으로 더 빠름	일관된 성능
적용 상황	메모리 제한적이고 평균 성능 중요	안정적 정렬과 일관된 성능 필요

퀵정렬과 병합정렬의 근본적인 차이는 분할과 병합의 방식과 공간 복잡도에 있습니다.

분할 방식:

•

퀵 정렬: 피벗을 기준으로 배열을 분할한 뒤, 각 부분 배열을 재귀적으로 정렬합니다. 병합 과정이 필요하지 않습니다.

•

병합 정렬: 배열을 균등하게 분할한 뒤, 병합 단계에서 정렬된 배열을 합칩니다.

병합 과정:

•

퀵 정렬: 병합 과정이 없으며, 분할 단계에서 정렬이 이루어집니다.

•

병합 정렬: 병합 단계에서 정렬된 배열을 합치며 정렬이 이루어집니다.

공간 복잡도:

•

퀵 정렬: 제자리 정렬(In-place Sort)로 추가 메모리 사용이 적으며, 공간 복잡도는 O(log n)입니다.

•

병합 정렬: 추가 배열이 필요하며, 공간 복잡도는 O(n)입니다.

최악 시간 복잡도:

•

퀵 정렬: 피벗 선택이 비효율적일 경우 O(n²)입니다.

•

병합 정렬: 항상 O(n log n)입니다.

퀵 정렬 순서도

graph TD;
A["배열을 분할"] --> B["피벗 기준으로 작은 값
배열로 나눈다"];
A --> C["피벗 기준으로 큰 값
배열로 나눈다"];
B --> D["크기 1이 될 때
까지 재귀적으로
나눈다"];
B --> E["크기 1이 될 때
까지 재귀적으로
나눈다"];
C --> F["크기 1이 될 때
까지 재귀적으로
나눈다"];
C --> G["크기 1이 될 때
까지 재귀적으로
나눈다"];
D --> H["작은 값 배열을 병합
하여 정렬된 배열을
만든다"];
E --> I["작은 값 배열을 병합
하여 정렬된 배열을
만든다"];
F --> J["큰 값 배열을 병합
하여 정렬된 배열을
만든다"];
G --> K["작은 값 배열을 병합
하여 정렬된 배열을
만든다"];
H --> L["정렬된 배열 완성"];
I --> L;
J --> L;
K --> L;
Mermaid
복사

재귀호출 실행 순서

mergeSort(arr, 0, 7)
 ├─ mergeSort(arr, 0, 3)
 │   ├─ mergeSort(arr, 0, 1)
 │   │   ├─ mergeSort(arr, 0, 0)  → (기저 조건 충족, 리턴)
 │   │   ├─ mergeSort(arr, 1, 1)  → (기저 조건 충족, 리턴)
 │   │   ├─ merge(arr, 0, 0, 1)   → 두 개의 정렬된 배열 병합
 │   │
 │   ├─ mergeSort(arr, 2, 3)
 │   │   ├─ mergeSort(arr, 2, 2)  → (기저 조건 충족, 리턴)
 │   │   ├─ mergeSort(arr, 3, 3)  → (기저 조건 충족, 리턴)
 │   │   ├─ merge(arr, 2, 2, 3)   → 두 개의 정렬된 배열 병합
 │   │
 │   ├─ merge(arr, 0, 1, 3)       → 두 개의 정렬된 배열 병합
 │
 ├─ mergeSort(arr, 4, 7)
 │   ├─ mergeSort(arr, 4, 5)
 │   │   ├─ mergeSort(arr, 4, 4)  → (기저 조건 충족, 리턴)
 │   │   ├─ mergeSort(arr, 5, 5)  → (기저 조건 충족, 리턴)
 │   │   ├─ merge(arr, 4, 4, 5)   → 두 개의 정렬된 배열 병합
 │   │
 │   ├─ mergeSort(arr, 6, 7)
 │   │   ├─ mergeSort(arr, 6, 6)  → (기저 조건 충족, 리턴)
 │   │   ├─ mergeSort(arr, 7, 7)  → (기저 조건 충족, 리턴)
 │   │   ├─ merge(arr, 6, 6, 7)   → 두 개의 정렬된 배열 병합
 │   │
 │   ├─ merge(arr, 4, 5, 7)       → 두 개의 정렬된 배열 병합
 │
 ├─ merge(arr, 0, 3, 7)           → 최종적으로 모든 부분을 병합

Java
복사

실행 순서대로 분할 및 병합 과정 (Merge Sort 과정 시뮬레이션)

병합 정렬은 "분할 (Divide)" 후 "병합 (Merge)" 과정이 진행됩니다.

아래 표에서는 분할과 병합을 동시에 실행 순서대로 정리했습니다.

1. 초기 배열

{45, 12, 89, 33, 76, 27, 8, 19}
Plain Text
복사

2. 분할 & 병합 과정

단계	분할 (Divide)	병합 (Merge)
①	{45, 12, 89, 33} {76, 27, 8, 19}
②	{45, 12} {89, 33} {76, 27} {8, 19}
③	{45} {12} {89} {33} {76} {27} {8} {19}
④		{12, 45} {33, 89} {27, 76} {8, 19}
⑤		{12, 33, 45, 89} {8, 19, 27, 76}
⑥		{8, 12, 19, 27, 33, 45, 76, 89}
(최종 정렬 완료)

3. 과정 상세 시각화

초기 상태: {45, 12, 89, 33, 76, 27, 8, 19}

1. 분할:  {45, 12, 89, 33}  |  {76, 27, 8, 19}
2. 분할:  {45, 12}  |  {89, 33}  |  {76, 27}  |  {8, 19}
3. 분할:  {45}  {12}  |  {89}  {33}  |  {76}  {27}  |  {8}  {19}
----------------------------------------------------
4. 병합:  {12, 45}  |  {33, 89}  |  {27, 76}  |  {8, 19}
5. 병합:  {12, 33, 45, 89}  |  {8, 19, 27, 76}
6. 병합:  {8, 12, 19, 27, 33, 45, 76, 89}  (최종 정렬 완료)

Plain Text
복사

4. 최종 결과

{8, 12, 19, 27, 33, 45, 76, 89}
Plain Text
복사

이처럼 병합 정렬은 분할(Divide) → 정렬 및 병합(Merge) 단계를 반복하며 정렬이 이루어집니다.