2025년 코딩테스트 정렬 알고리즘 총정리: 면접 합격까지 한번에 끝내기

코딩테스트를 준비하면서 가장 중요한 부분 중 하나가 정렬 알고리즘입니다. 사실 저도 처음에는 "그냥 sort() 함수를 쓰면 되지 않나?"라고 생각했는데, 여러 회사의 기술면접을 겪으면서 정렬 알고리즘의 개념과 구현을 직접 할 수 있어야 한다는 것을 깨달았습니다.

 

이 글에서는 코딩테스트와 면접에서 꼭 알아야 하는 정렬 알고리즘들을 실제로 구현하는 방법부터, 각 알고리즘의 장단점, 그리고 어떤 상황에서 어떤 알고리즘을 써야 하는지까지 실전 팁을 정리했습니다. 저도 공부하면서 정리한 내용이라 실무에서도 자주 쓰이는 실용적인 정보들을 담았습니다.

정렬 알고리즘의 기초: 왜 배워야 할까?

코딩테스트에서 정렬은 거의 모든 문제에서 나타나는 개념입니다. 특히 백준이나 프로그래머스의 많은 문제들이 "데이터를 정렬한 후 다음 작업을 수행하라"는 형태로 출제됩니다.

 

면접 관점에서는 더 중요한데, 면접관들은 정렬 알고리즘의 구현을 통해 당신의 알고리즘 이해도, 코드 구현 능력, 그리고 문제 해결 능력을 종합적으로 평가합니다. 따라서 최소 3개 이상의 정렬 알고리즘(버블 정렬, 퀵 정렬, 병합 정렬)은 완벽하게 구현할 수 있어야 합니다.

 

정렬 알고리즘 선택의 핵심 포인트

정렬 알고리즘을 배울 때 가장 중요한 것은 시간복잡도입니다. 각 알고리즘의 최선, 평균, 최악의 경우를 이해해야 합니다. 또한 데이터의 크기, 분포, 메모리 제약 등에 따라 선택이 달라집니다. 예를 들어, 이미 거의 정렬된 데이터라면 삽입 정렬이 퀵 정렬보다 훨씬 빠를 수 있습니다.

O(n²) 정렬 알고리즘: 기초부터 탄탄히

코딩테스트에서 O(n²) 정렬은 거의 사용되지 않지만, 면접에서는 "가장 간단한 정렬부터 설명해보세요"라는 질문이 자주 나옵니다. 따라서 이 부분을 명확하게 이해하는 것이 중요합니다.

 

버블 정렬(Bubble Sort)

버블 정렬은 인접한 두 원소를 반복적으로 비교하면서 큰 값을 뒤로 이동시키는 알고리즘입니다. 마치 물이 끓을 때 거품이 올라오는 것처럼 동작해서 이런 이름이 붙었습니다.

• 첫 번째 순회: 가장 큰 원소가 맨 끝으로 이동
• 두 번째 순회: 두 번째로 큰 원소가 끝에서 두 번째로 이동
• 이 과정을 반복

시간복잡도
- 최선: O(n)
- 평균: O(n²)
- 최악: O(n²)

 

Java 구현

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }
}

 

Python 구현

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

 

면접 팁: 버블 정렬을 설명할 때는 "왜 O(n²)의 시간복잡도가 나오는가?"를 반드시 언급하세요.

 

선택 정렬(Selection Sort)

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

 

삽입 정렬(Insertion Sort)

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; 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;
        }
    }
}

O(n log n) 정렬 알고리즘: 실전의 주인공들

퀵 정렬(Quick Sort)

public class QuickSort {
    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);
        }
    }
    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;
    }
}

 

병합 정렬(Merge Sort)

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    private static void merge(int[] arr, int left, int mid, int right) {
        int leftSize = mid - left + 1;
        int rightSize = right - mid;
        int[] L = new int[leftSize];
        int[] R = new int[rightSize];
        for (int i = 0; i < leftSize; i++) L[i] = arr[left + i];
        for (int j = 0; j < rightSize; j++) R[j] = arr[mid + 1 + j];
        int i = 0, j = 0, k = left;
        while (i < leftSize && j < rightSize) {
            if (L[i] <= R[j]) arr[k++] = L[i++];
            else arr[k++] = R[j++];
        }
        while (i < leftSize) arr[k++] = L[i++];
        while (j < rightSize) arr[k++] = R[j++];
    }
}

 

힙 정렬(Heap Sort)

public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;
        for (int i = n/2 - 1; i >= 0; i--) heapify(arr, n, i);
        for (int i = n-1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    private static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2*i + 1;
        int right = 2*i + 2;
        if (left < n && arr[left] > arr[largest]) largest = left;
        if (right < n && arr[right] > arr[largest]) largest = right;
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
        }
    }
}

O(n) 정렬: 계수 정렬

public class CountingSort {
    public static void countingSort(int[] arr, int maxValue) {
        int[] count = new int[maxValue + 1];
        for (int num : arr) count[num]++;
        int idx = 0;
        for (int i = 0; i <= maxValue; i++)
            for (int j = 0; j < count[i]; j++)
                arr[idx++] = i;
    }
}

실전 팁: 알고리즘 선택 기준

• 데이터 범위가 좁으면 → 계수 정렬
• 빠른 일반 정렬 → 퀵 정렬
• 안정성 중요 → 병합 정렬
• 메모리 제한 → 힙 정렬
• 거의 정렬된 데이터 → 삽입 정렬

정렬 알고리즘은 단순히 데이터를 정렬하는 기술을 넘어, 모든 알고리즘의 기본 사고방식을 익히는 출발점입니다. 퀵 정렬과 병합 정렬을 손으로 구현해보며 확실히 체득해보세요. 꾸준히 연습하면 코딩테스트 뿐만 아니라 면접에서도 큰 자신감을 갖게 될 것입니다.

 

코딩테스트 한 문제를 여러 풀이로 접근하기 - 실무적 해석력 키우기