정렬 알고리즘 완전 정복 - O(N²)부터 O(N log N)까지, 정렬 알고리즘 비교

📌 1. 정렬이란? 왜 중요한가?

• 정렬이 필요한 이유 (예시: 탐색 최적화, 데이터 처리)
• 실제 활용 예시: 데이터베이스 인덱싱, 코딩 테스트, AI 데이터 전처리

---

📌 2. 정렬 알고리즘 분류

유형정렬 알고리즘시간복잡도특징

O(N²) (기본 정렬)	버블 정렬, 선택 정렬, 삽입 정렬	O(N²)	느림, 기초 개념 익히기 좋음
O(N log N) (고급 정렬)	퀵 정렬, 병합 정렬, 힙 정렬	O(N log N)	실전에서 많이 사용
O(N) (특수 정렬)	카운팅 정렬, 기수 정렬, 버킷 정렬	O(N)	특정 조건에서만 사용 가능

---

📌 3. 기본 정렬 알고리즘 (O(N²))

✅ 3-1. 버블 정렬 (Bubble Sort)

• 개념: 인접한 두 원소를 비교하여 교환하는 방식
• 시간복잡도: O(N²)
• 특징: 구현은 쉽지만 비효율적
• Java 구현 예제

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

 

✅ 3-2. 선택 정렬 (Selection Sort)

• 개념: 가장 작은 값을 찾아 맨 앞과 교환
• 시간복잡도: O(N²)
• 특징: 항상 일정한 시간복잡도를 가짐
• Java 구현 예제

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
    }
}

✅ 3-3. 삽입 정렬 (Insertion Sort)

• 개념: 앞쪽 부분은 정렬된 상태를 유지하면서 삽입
• 시간복잡도: O(N²) (최선의 경우 O(N))
• 특징: 거의 정렬된 데이터에 강함
• Java 구현 예제

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

---

📌 4. 고급 정렬 알고리즘 (O(N log N))

✅ 4-1. 퀵 정렬 (Quick Sort)

• 개념: 분할 정복(피벗을 기준으로 좌우 분할)
• 시간복잡도: 평균 O(N log N), 최악 O(N²)
• 특징: 가장 많이 사용되는 정렬
• Java 구현 예제

public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;

    int pivot = partition(arr, left, right);
    quickSort(arr, left, pivot - 1);
    quickSort(arr, pivot + 1, right);
}

public static int partition(int[] arr, int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, right);
    return i + 1;
}

✅ 4-2. 병합 정렬 (Merge Sort)

• 개념: 분할 정복(배열을 절반으로 나누어 정렬 후 합치기)
• 시간복잡도: O(N log N)
• 특징: 항상 O(N log N) 보장 (퀵 정렬보다 안정적)
• Java 구현 예제

public static void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;

    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

---

📌 5. 정렬 알고리즘 비교 분석

정렬 알고리즘평균 시간복잡도최악 시간복잡도특징

버블 정렬	O(N²)	O(N²)	느림
선택 정렬	O(N²)	O(N²)	항상 일정
삽입 정렬	O(N²)	O(N²)	거의 정렬된 경우 O(N)
퀵 정렬	O(N log N)	O(N²)	빠름, 실전에서 많이 사용
병합 정렬	O(N log N)	O(N log N)	안정적이지만 추가 메모리 필요
힙 정렬	O(N log N)	O(N log N)	추가 메모리 없이 일정한 성능

---

📌 6. 실전에서 어떤 정렬을 사용할까?

1. 일반적인 경우
   • Arrays.sort(arr) → 내부적으로 퀵 정렬 + 병합 정렬 조합 (O(N log N))
2. 대량의 데이터 & 안정 정렬 필요
   • 병합 정렬 (Merge Sort)
3. 힙을 활용한 정렬 필요 (우선순위 큐)
   • 힙 정렬 (Heap Sort)

---

✅ 결론

🔥 정렬 알고리즘은 실전에서 꼭 필요한 기술!

• 정렬 알고리즘을 이해하면 탐색, 최적화, 문제 해결 능력이 향상됨
• 코딩 테스트에서는 퀵 정렬, 병합 정렬, 힙 정렬을 익혀두자!