[개발자의 알고리즘 서랍] 첫 번째: '정렬' 을 꺼내다

Posted Jul 14, 2025

By Jo Jin Woo

24 min read

코딩 테스트에서 정렬 문제를 마주했을 때, ‘어떤 정렬을 써야 할까?’ 고민하다 보면 소중한 시간이 흘러갑니다. Arrays.sort()가 대부분의 경우 효과적이지만, 모든 상황에 맞는 만능 열쇠는 아니기에 때로는 다른 접근이 필요할 수 있습니다.

이 글은 실전에서 유용한 정렬 전략을 세우는 데 도움이 될 수 있는 핵심 원칙과 기준을 제시합니다. 내장 함수를 언제 신뢰하면 좋은지, 그리고 어떤 상황에서 직접 구현이 더 효과적인 선택이 될 수 있는지 함께 살펴보겠습니다.

✨ 이 글의 학습 목표

Arrays.sort()가 언제, 왜 빠른지 그 동작 원리를 근거로 설명합니다.
퀵, 병합, 힙 정렬의 장단점을 분석하여, 특정 상황에 어떤 정렬이 더 유리할지 판단합니다.
Comparator를 사용하여 문제에서 요구하는 까다로운 조건의 객체 정렬을 능숙하게 구현합니다.
‘안정성’과 ‘메모리’라는 기준을 통해, 문제의 숨은 제약조건에 가장 적합한 정렬 알고리즘을 선택합니다.

1. 실전 코딩 테스트, 어떤 정렬을 써야 할까?

1.1. 현명한 첫 번째 선택: 내장 정렬 함수 활용하기

코딩 테스트에서 정렬이 필요하다면, 우선 Arrays.sort()나 Collections.sort() 사용을 고려하는 것이 좋습니다. 직접 정렬 알고리즘을 구현하는 것은 특정 목적이 있거나 문제에서 명시적으로 요구하는 경우에 고려해볼 수 있습니다. 내장 함수는 일반적으로 전문가들이 검증하고 최적화한, 신뢰도 높고 효율적인 방법 중 하나입니다.

Java의 내장 정렬은 데이터 타입에 따라 지능적으로 다른 알고리즘을 사용하는 경향이 있습니다.

🔢 단순 숫자 배열을 정렬할 때 (`int[]`, `double[]` 등)

핵심 목표: 🚀 오직 속도!

마구 섞인 숫자 카드 더미를 가장 빠르게 순서대로 놓는 것과 같아요. 똑같은 숫자 7 카드가 여러 장 있어도 어느 7이 먼저인지는 전혀 중요하지 않죠.
이처럼 값 자체만 중요할 땐, Java는 평균 속도가 가장 빠른 것으로 알려진 듀얼 피봇 퀵 정렬(Dual-Pivot Quick Sort)을 사용해 속도에 집중합니다.

🧑‍🤝‍🧑 객체 배열을 정렬할 때 (`Student[]`, `String[]` 등)

핵심 목표: 🤝 안정성 + 효율!

‘학생 명단’을 ‘성적순’으로 정렬하는 상황을 생각해 보세요. 만약 동점자가 있다면, 원래 명단에 먼저 이름이 있던 학생이 정렬 후에도 앞에 오는 게 상식적이겠죠? 이렇게 값이 같을 때 원래 순서를 지켜주는 것이 바로 안정성(Stability)입니다.
이처럼 순서 유지가 중요할 수 있기에, Java는 안정성을 완벽히 보장하면서도 매우 효율적인 팀소트(Timsort)라는 방식을 사용합니다.

1.2. 직접 구현을 고려해볼 만한 경우

상황 1: 데이터 값의 범위가 매우 작을 때 (예: 0~1000)
- 선택: 계수 정렬 (Counting Sort)
- 이유: 조건이 맞으면 O(N) 수준의 매우 빠른 속도를 기대할 수 있습니다.
상황 2: 정렬 과정 자체를 응용해야 할 때 (예: 역순 쌍 개수 세기)
- 선택: 병합 정렬 (Merge Sort)
- 이유: ‘분할-병합’ 구조가 특정 문제 풀이에 유용한 힌트가 될 수 있습니다.

2. 정렬 알고리즘을 평가하는 2가지 기준

정렬 알고리즘의 특징을 파악할 때, 아래 두 가지 기준을 이해하면 도움이 됩니다.

2.1. 제자리 정렬 (In-place Sort)

정의: 정렬에 필요한 추가 메모리 공간의 크기가 입력 데이터 크기와 무관하게 일정한(O(1) 또는 O(logN)) 정렬 방식을 의미합니다.
비유: 큰 창고 없이 내 방 안에서 물건을 정리하는 것에 비유할 수 있습니다. 데이터를 담을 별도의 큰 배열을 만들지 않으므로 메모리 사용이 효율적입니다.
대표 알고리즘: 선택 정렬, 삽입 정렬, 힙 정렬, 퀵 정렬 등

2.2. 안정 정렬 (Stable Sort)

정의: 중복된 값들의 기존 순서가 정렬 후에도 그대로 유지되는 정렬 방식을 말합니다.
비유: 학생 명부를 성적순으로 정렬할 때, 동점자들은 원래 명부의 순서를 그대로 유지하는 것과 같습니다. 여러 기준으로 순차 정렬할 때 중요한 특성이 될 수 있습니다.
대표 알고리즘: 삽입 정렬, 병합 정렬, 계수 정렬 등

3. 기초 다지기: O(N²) 알고리즘

3.1. 선택 정렬 (Selection Sort)

특징: 제자리 정렬, 불안정 정렬
원리: 전체 데이터에서 가장 작은 값을 찾아 맨 앞 데이터와 교환하는 과정을 반복합니다.
장점: 구현이 직관적이고 추가 메모리가 거의 필요 없습니다.
단점: 데이터의 정렬 상태와 무관하게 항상 전체를 비교하므로 대체로 비효율적입니다.

핵심 코드 로직 (Java)

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

3.2. 삽입 정렬 (Insertion Sort)

특징: 제자리 정렬, 안정 정렬
원리: 새로운 데이터를 이미 정렬된 부분의 올바른 위치에 삽입하는 과정을 반복합니다.
장점: 데이터가 거의 정렬된 경우 매우 빠르며 안정적입니다.
단점: 역순으로 정렬된 경우 최악의 성능을 보일 수 있습니다.

핵심 코드 로직 (Java)

  
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;
    }
}

4. 코딩 테스트 핵심 무기: O(N log N) 알고리즘

4.1. 병합 정렬 (Merge Sort)

특징: 안정 정렬, 제자리 정렬 ❌
원리: ‘분할 정복’ - 데이터를 더 이상 쪼갤 수 없을 때까지 반으로 나눈 뒤, 다시 정렬하며 병합합니다.
장점: 항상 O(NlogN) 성능을 보장하는 경향이 있으며 안정적입니다.
단점: 정렬을 위한 임시 배열이 필요해 $O(N)$의 추가 공간을 사용합니다.

핵심 코드 로직 (Java)

  
// 재귀적으로 호출되는 mergeSort 함수
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);
    }
}

// 두 부분을 병합하는 함수
void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    for (int idx = 0; idx < temp.length; idx++) {
        arr[left + idx] = temp[idx];
    }
}

4.2. 퀵 정렬 (Quick Sort)

특징: 제자리 정렬, 불안정 정렬
원리: ‘분할 정복’ - 기준(pivot)을 정하고, pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮겨 리스트를 분할하는 과정을 재귀적으로 반복합니다.
장점: 평균적으로 매우 빠른 성능을 보이며, 제자리에서 정렬이 가능합니다.
단점: 최악의 경우 성능이 $O(N^2)$까지 저하될 수 있으며 불안정합니다.

핵심 코드 로직 (Java)

  
// 재귀적으로 호출되는 quickSort 함수
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);
    }
}

// 배열을 분할하고 pivot의 위치를 반환하는 함수
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;
}

4.3. 힙 정렬 (Heap Sort)

특징: 제자리 정렬, 불안정 정렬
원리: 최대 힙을 구성한 후, 루트 노드(최댓값)를 하나씩 추출하여 배열의 뒤부터 채워나갑니다.
장점: 항상 O(NlogN) 성능을 기대할 수 있으며, 제자리 정렬이 가능합니다.
단점: 실제 평균 성능은 퀵 정렬보다 느린 경우가 많습니다.

핵심 코드 로직 (Java)

  
void heapSort(int[] arr) {
    int n = arr.length;
    // 힙 구성 (Build Heap)
    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);
    }
}

void heapify(int[] arr, int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;

    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;
        heapify(arr, n, largest);
    }
}

5. 정렬, 더 깊이 이해하기

5.1. 정렬 알고리즘 한눈에 비교하기

알고리즘	평균 시간 복잡도	최악 시간 복잡도	공간 복잡도	안정성(Stable)	특징
선택 정렬	O(N2)	O(N2)	O(1)	❌	구현이 비교적 간단하지만 비효율적일 수 있음
삽입 정렬	O(N2)	O(N2)	O(1)	✅	거의 정렬된 데이터에 매우 빠름 (O(N))
병합 정렬	O(NlogN)	O(NlogN)	O(N)	✅	성능이 안정적, 안정 정렬이 필요할 때 좋은 선택
퀵 정렬	O(NlogN)	O(N2)	O(logN)	❌	평균적으로 빠른 속도, 제자리 정렬
힙 정렬	O(NlogN)	O(NlogN)	O(1)	❌	제자리 정렬이면서 안정적인 성능 보장
계수 정렬	O(N+k)	O(N+k)	O(k)	✅	값의 범위가 작을 때 매우 효율적, 비-비교 방식

k는 데이터 값의 범위를 의미합니다.

5.2. 안정 정렬(Stable Sort)의 실전 활용

안정 정렬은 여러 기준으로 데이터를 정렬할 때 유용합니다. 예를 들어, 상품을 1. 가격 오름차순으로 정렬한 후, 다시 2. 등록일 최신순으로 정렬한다고 가정해 봅시다. 만약 두 번째 정렬이 불안정하다면, 같은 날 등록된 상품들의 가격 순서가 뒤섞일 수 있습니다. 안정 정렬은 같은 날 등록된 상품들이 이전에 정렬된 가격순을 그대로 유지하도록 보장해 줍니다.

5.3. 정렬의 이론적 한계와 비-비교 정렬

비교 기반 정렬의 한계: 결정 트리(Decision Tree) 모델에 따르면, 원소들을 두 개씩 비교하는 방식으로는 최악의 경우 최소 Omega(NlogN) 번의 비교가 필요하다고 알려져 있습니다. 이것이 비교 기반 정렬의 이론적인 시간 복잡도 하한선으로 여겨집니다.
한계 돌파 (비-비교 정렬): 계수 정렬, 기수 정렬 등은 원소를 직접 비교하지 않고 값 자체의 특성(분포, 자릿수 등)을 활용합니다. 이러한 방식 덕분에 특정 조건 하에서 $O(N \log N)$의 한계를 넘어설 수 있습니다.

5.4. 정렬의 변형과 응용

부분 정렬 (Partial Sorting): 전체가 아닌 상위 K개만 필요할 때 사용합니다. (퀵 셀렉트, 힙 활용)
외부 정렬 (External Sorting): 메모리에 다 담을 수 없는 대용량 데이터를 정렬합니다. (데이터를 작은 청크로 나눠 정렬 후 병합)
스트리밍 데이터 정렬: 실시간으로 들어오는 데이터의 중앙값을 유지하는 등의 문제에 활용될 수 있습니다. (두 개의 힙 사용)

6. 실전 문제 풀이와 팁

6.1. `Comparator`로 나만의 정렬 기준 만들기

Arrays.sort에 Comparator를 전달하면 원하는 기준으로 객체를 정렬할 수 있습니다. 람다식을 활용하면 코드를 간결하게 작성하는 데 도움이 됩니다.

  
// 2D 배열 정렬 예시
int[][] points = { {1, 3}, {2, 1}, {1, 1} };

// x좌표 오름차순, x가 같으면 y좌표 오름차순으로 정렬
// 참고: a[0] - b[0] 방식은 오버플로우를 유발할 수 있으므로,
// Integer.compare(a, b)를 사용하는 것이 더 안전합니다.
Arrays.sort(points, (a, b) -> {
    if (a[0] != b[0]) {
        return Integer.compare(a[0], b[0]);
    }
    return Integer.compare(a[1], b[1]);
});

6.2. 코딩 테스트 정렬 문제의 흔한 함정

알고리즘을 선택하고 구현하는 과정에서 몇 가지 흔한 실수가 시간 초과나 오답으로 이어질 수 있습니다. 다음 함정들을 유의하면 좋습니다.

함정 1: 데이터 크기를 고려하지 않고 O(N2) 알고리즘 사용하기
- 선택 정렬이나 삽입 정렬은 구현이 간단하지만, 데이터의 개수(N)가 100,000개 수준으로 주어지면 거의 100% 시간 초과가 발생합니다. 문제의 제약 조건(예: Nle100,000)을 가장 먼저 확인하고, N이 크다면 O(NlogN) 정렬을 사용해야 합니다.
함정 2: Comparator 구현 시 정수 오버플로우(Integer Overflow) 발생
- 두 정수를 비교하기 위해 return o1 - o2; 와 같은 코드를 사용하는 경우가 많습니다. 이 방식은 코드가 간결하지만, 두 수의 차이가 Integer의 표현 범위를 넘어서면 오버플로우가 발생하여 정렬 순서가 완전히 꼬일 수 있습니다.
- 안전한 방법: Integer.compare(o1, o2)를 사용하거나, if-else 문으로 직접 비교하는 것이 가장 안전하고 바람직합니다.

  
    // ⚠️ 위험한 방식 (오버플로우 가능성)
    Arrays.sort(scores, (a, b) -> a - b);
    
    // ✅ 안전한 방식
    Arrays.sort(scores, (a, b) -> Integer.compare(a, b));
    // 또는
    Arrays.sort(scores, Comparator.naturalOrder());

함정 3: 안정 정렬(Stable Sort)이 꼭 필요한지 놓치기
- “1차 기준(예: 점수)으로 정렬하고, 1차 기준이 같으면 2차 기준(예: 나이)은 원래 순서를 유지하라”와 같은 요구사항은 안정 정렬이 필요하다는 신호입니다. 이때 불안정 정렬인 퀵 정렬 등을 직접 구현해 사용하면 의도치 않은 결과가 나올 수 있습니다. Java의 Collections.sort()나 객체 배열에 대한 Arrays.sort()(팀소트)는 안정 정렬을 보장하므로 안심하고 사용할 수 있습니다.

마치며

결국 정렬의 핵심은 ‘그래서 지금 뭘 써야 하지?’라는 질문에 자신 있게 답할 수 있는 ‘감’을 기르는 데 있는 것 같아요.

코딩 테스트에서 문제를 마주쳤을 때, ‘데이터 개수가 몇 개지?’, ‘혹시 안정 정렬이 필요한가?’ 같은 몇 가지 기준만 바로 떠올릴 수 있어도 절반은 성공입니다. Arrays.sort()는 정말 강력한 도구지만, 언제 믿고 맡겨야 할지, 또 어떨 때 다른 대안을 꺼내야 할지 알 때 진짜 실력이 되니까요.

이 글이 여러분이 그런 ‘감’을 잡고, 어떤 정렬 문제 앞에서도 조금 더 자신감을 갖는 데 도움이 되었으면 좋겠습니다.

알고리즘

This post is licensed under CC BY 4.0 by the author.

✨ 이 글의 학습 목표

1. 실전 코딩 테스트, 어떤 정렬을 써야 할까?

1.1. 현명한 첫 번째 선택: 내장 정렬 함수 활용하기

🔢 단순 숫자 배열을 정렬할 때 (int[], double[] 등)

🧑‍🤝‍🧑 객체 배열을 정렬할 때 (Student[], String[] 등)

1.2. 직접 구현을 고려해볼 만한 경우

2. 정렬 알고리즘을 평가하는 2가지 기준

2.1. 제자리 정렬 (In-place Sort)

2.2. 안정 정렬 (Stable Sort)

3. 기초 다지기: O(N²) 알고리즘

3.1. 선택 정렬 (Selection Sort)

핵심 코드 로직 (Java)

3.2. 삽입 정렬 (Insertion Sort)

핵심 코드 로직 (Java)

4. 코딩 테스트 핵심 무기: O(N log N) 알고리즘

4.1. 병합 정렬 (Merge Sort)

핵심 코드 로직 (Java)

4.2. 퀵 정렬 (Quick Sort)

핵심 코드 로직 (Java)

4.3. 힙 정렬 (Heap Sort)

핵심 코드 로직 (Java)

5. 정렬, 더 깊이 이해하기

5.1. 정렬 알고리즘 한눈에 비교하기

5.2. 안정 정렬(Stable Sort)의 실전 활용

5.3. 정렬의 이론적 한계와 비-비교 정렬

5.4. 정렬의 변형과 응용

6. 실전 문제 풀이와 팁

6.1. Comparator로 나만의 정렬 기준 만들기

6.2. 코딩 테스트 정렬 문제의 흔한 함정

마치며

Trending Tags

🔢 단순 숫자 배열을 정렬할 때 (`int[]`, `double[]` 등)

🧑‍🤝‍🧑 객체 배열을 정렬할 때 (`Student[]`, `String[]` 등)

6.1. `Comparator`로 나만의 정렬 기준 만들기