💻 [자료구조] 정렬 알고리즘 총정리

🎯 개요

정렬 알고리즘은 데이터를 일정한 순서로 배열하는 기본 개념이지만,
알고리즘에 따라 성능 차이가 크고, 실무 성능 개선에 직접 연결되는 중요한 주제입니다.

이번 정리는 각각의 정렬 방식을 자바 코드로 구현하고,
시간복잡도 및 정렬 흐름을 직접 실험하며 이해한 내용을 기반으로 구성했습니다.

---

📌 정렬 알고리즘 분류

유형	알고리즘	특징
단순 비교 정렬	버블, 선택, 삽입 정렬	구현이 쉽고 직관적, 성능은 낮음
고급 정렬	퀵, 병합, 힙 정렬	실무 적용 가능, 성능 우수
안정 정렬 여부	병합, 삽입 (O) / 퀵, 선택 (X)	동일한 값의 순서를 보존하는가 여부

---

🧮 버블 정렬 (Bubble Sort)

옆에 있는 값과 비교해 swap, 큰 값이 뒤로 밀려남

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 tmp = arr[j]; 
                arr[j] = arr[j + 1]; 
                arr[j + 1] = tmp;
            }
        }
    }
}

 

• 시간복잡도: O(n²)
• 특징: 구현은 쉽지만 매우 느림

---

 

✍️ 선택 정렬 (Selection Sort)

가장 작은 값을 골라 맨 앞에 위치시킴

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

 

• 시간복잡도: O(n²)
• 특징: 교환 횟수는 적지만 안정 정렬이 아님

---

 

🧲 삽입 정렬 (Insertion Sort)

앞쪽은 정렬된 상태라 가정하고, 뒤에서 삽입 위치를 찾아 삽입

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

• 시간복잡도: O(n²) (하지만 거의 정렬된 경우 빠름)
• 특징: 안정 정렬, 실무에서 간단한 정렬에 사용 가능

---

⚡ 퀵 정렬 (Quick Sort)

피벗을 기준으로 좌우를 분할해 정렬 (분할 정복)

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

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

• 평균 시간복잡도: O(n log n) / 최악: O(n²)
• 특징: 실무에서 가장 많이 사용됨 (빠르고 구현 쉬움)

---

⚙️ 병합 정렬 (Merge Sort)

배열을 절반으로 나눠 각각 정렬 후 병합 (분할 정복)

 

void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void merge(int[] arr, int left, int mid, int right) {
    int[] tmp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        tmp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= right) tmp[k++] = arr[j++];

    for (int x = 0; x < tmp.length; x++) arr[left + x] = tmp[x];
}

• 시간복잡도: O(n log n) (항상 일정)
• 특징: 안정 정렬, 병렬처리 가능

---

🔧 힙 정렬 (Heap Sort)

Heap 자료구조를 사용하여 정렬 (우선순위 큐 기반)

void heapSort(int[] arr) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int num : arr) pq.add(num);

    int i = 0;
    while (!pq.isEmpty()) {
        arr[i++] = pq.poll();
    }
}

 

• 시간복잡도: O(n log n)
• 특징: 추가 메모리 사용 적고, 안정 정렬은 아님

---

📋 정렬 알고리즘 비교표

알고리즘	평균 시간복잡도	공간복잡도	안정 정렬	특징
버블 정렬	O(n²)	O(1)	O	가장 비효율적
선택 정렬	O(n²)	O(1)	X	교환 횟수 적음
삽입 정렬	O(n²)	O(1)	O	거의 정렬된 데이터에 빠름
퀵 정렬	O(n log n)	O(log n)	X	실무에서 가장 많이 사용
병합 정렬	O(n log n)	O(n)	O	안정적, 예측 가능
힙 정렬	O(n log n)	O(1)	X	우선순위 기반 정렬

---

✍️ 마무리 요약

• 퀵 정렬은 평균 성능이 좋고, 배열 기반 시스템에서 가장 많이 활용됨
• 병합 정렬은 안정성이 중요하거나 병렬 처리가 필요한 경우 적합
• 삽입 정렬은 작은 데이터나 거의 정렬된 경우 유용
• 우선순위가 중요한 상황(스케줄링 등)에서는 힙 정렬이 활용 가능

정렬 알고리즘은 단순 구현 문제가 아니라,
데이터 특성과 처리 조건에 따라 최적 알고리즘을 선택하는 감각이 중요합니다.

---

📚 추가 자료

전체 코드 및 실습 예제는 👉 GitHub - mingstagram/daily-cs-study 에 정리되어 있습니다.