[알고리즘] 33. 정렬 알고리즘 개념

[알고리즘] 33. 정렬 알고리즘 개념

지난 글에서는 최단 거리 기초에 대해 정리했습니다. 이번 글부터는 정렬과 구간 처리 영역으로 들어갑니다. 그 첫 번째 주제는 정렬 알고리즘 개념입니다.

정렬은 데이터를 일정한 기준에 따라 순서대로 나열하는 작업입니다. 알고리즘 문제에서는 숫자를 작은 순서대로 정렬하거나, 문자열을 사전순으로 정렬하거나, 여러 조건에 맞게 데이터를 정리할 때 자주 사용됩니다.

정렬은 데이터를 원하는 기준에 맞게 순서대로 배치하는 알고리즘입니다.

---

1. 정렬이란?

정렬은 여러 데이터를 특정 기준에 따라 순서대로 배치하는 것입니다. 가장 기본적인 예시는 숫자 정렬입니다.

정렬 전: 5 2 8 1 3
정렬 후: 1 2 3 5 8

위 예시는 숫자를 작은 값에서 큰 값 순서로 정렬한 것입니다. 이처럼 정렬은 데이터를 보기 좋게 만드는 것뿐 아니라, 이후 탐색이나 계산을 더 쉽게 만들기 위해 사용됩니다.

정렬은 단순히 순서를 바꾸는 작업이 아니라, 문제 해결을 쉽게 만드는 준비 과정이 될 수 있습니다.

---

2. 정렬이 필요한 이유

알고리즘 문제에서 정렬은 매우 자주 사용됩니다. 정렬을 하면 데이터의 순서가 정리되기 때문에 문제를 더 쉽게 풀 수 있습니다.

• 최솟값과 최댓값을 쉽게 찾을 수 있다.
• 중복 값을 가까이 모을 수 있다.
• 이분 탐색을 사용할 수 있다.
• 순위를 계산할 수 있다.
• 투 포인터를 사용할 수 있다.
• 그리디 문제에서 선택 기준을 만들 수 있다.

예를 들어 정렬되지 않은 배열에서 중복 값을 찾으려면 여러 번 비교해야 할 수 있습니다. 하지만 정렬하면 같은 값이 서로 가까이 붙기 때문에 중복 확인이 훨씬 쉬워집니다.

정렬 전: 3 1 4 2 3
정렬 후: 1 2 3 3 4

3이 서로 붙어 있으므로 중복 확인이 쉬워짐

---

3. 오름차순과 내림차순

정렬의 가장 기본적인 기준은 오름차순과 내림차순입니다.

구분	의미	예시
오름차순	작은 값에서 큰 값 순서	1, 2, 3, 4, 5
내림차순	큰 값에서 작은 값 순서	5, 4, 3, 2, 1

문제에서 특별한 말이 없다면 보통 오름차순 정렬을 기준으로 생각하는 경우가 많습니다. 하지만 “큰 순서대로”, “점수가 높은 순서대로”, “가장 큰 값부터” 같은 표현이 있다면 내림차순 정렬을 고려해야 합니다.

정렬 문제를 보면 먼저 오름차순인지 내림차순인지부터 확인해야 합니다.

---

4. 정렬 알고리즘의 종류

정렬 알고리즘은 여러 종류가 있습니다. 입문 단계에서는 먼저 기본 정렬 알고리즘의 흐름을 이해하는 것이 중요합니다.

정렬 알고리즘	핵심 아이디어
선택 정렬	가장 작은 값을 찾아 앞쪽으로 보냄
버블 정렬	인접한 두 값을 비교하며 큰 값을 뒤로 보냄
삽입 정렬	현재 값을 이미 정렬된 구간의 알맞은 위치에 삽입
병합 정렬	나누고 정렬한 뒤 다시 합침
퀵 정렬	기준값을 중심으로 작은 값과 큰 값을 나눔

실제 Java에서는 직접 정렬 알고리즘을 구현하기보다 Arrays.sort() 같은 내장 정렬을 자주 사용합니다. 하지만 정렬 알고리즘의 기본 흐름을 이해하면 시간복잡도와 문제 풀이 전략을 더 잘 이해할 수 있습니다.

---

5. 선택 정렬 개념

선택 정렬은 배열에서 가장 작은 값을 찾아 맨 앞의 값과 바꾸는 방식입니다. 그다음 두 번째 위치부터 다시 가장 작은 값을 찾아 바꿉니다.

정렬 전: 5 2 8 1 3

1회전: 가장 작은 값 1을 찾아 첫 번째 위치로 이동
결과: 1 2 8 5 3

2회전: 남은 구간에서 가장 작은 값 2는 이미 제자리
결과: 1 2 8 5 3

3회전: 남은 구간에서 가장 작은 값 3을 앞으로 이동
결과: 1 2 3 5 8

선택 정렬은 이해하기 쉽지만, 매번 남은 구간을 끝까지 확인해야 하므로 데이터가 많아지면 느려집니다.

선택 정렬은 가장 작은 값을 선택해서 앞쪽부터 채워나가는 정렬입니다.

---

6. 선택 정렬 Java 코드

선택 정렬을 Java 코드로 작성하면 다음과 같습니다.

int[] arr = {5, 2, 8, 1, 3};

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[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
}

for (int num : arr) {
    System.out.print(num + " ");
}

출력 결과는 다음과 같습니다.

1 2 3 5 8

바깥 반복문은 정렬할 위치를 정하고, 안쪽 반복문은 그 위치에 들어갈 가장 작은 값을 찾습니다.

---

7. 버블 정렬 개념

버블 정렬은 인접한 두 값을 비교하면서 큰 값을 뒤로 보내는 방식입니다. 큰 값이 오른쪽으로 밀려 올라가는 모습이 거품처럼 보인다고 해서 버블 정렬이라고 부릅니다.

정렬 전: 5 2 8 1 3

5와 2 비교 → 5가 더 크므로 교환
2 5 8 1 3

5와 8 비교 → 그대로
2 5 8 1 3

8과 1 비교 → 8이 더 크므로 교환
2 5 1 8 3

8과 3 비교 → 8이 더 크므로 교환
2 5 1 3 8

한 번의 회전이 끝나면 가장 큰 값이 맨 뒤로 이동합니다. 이 과정을 반복하면 배열이 정렬됩니다.

버블 정렬은 인접한 값을 비교하며 큰 값을 뒤로 보내는 정렬입니다.

---

8. 버블 정렬 Java 코드

버블 정렬을 Java 코드로 작성하면 다음과 같습니다.

int[] arr = {5, 2, 8, 1, 3};

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

for (int num : arr) {
    System.out.print(num + " ");
}

출력 결과는 다음과 같습니다.

1 2 3 5 8

안쪽 반복문에서 arr[j]와 arr[j + 1]을 비교합니다. 왼쪽 값이 더 크면 두 값을 교환합니다.

---

9. 삽입 정렬 개념

삽입 정렬은 현재 값을 이미 정렬된 구간의 알맞은 위치에 넣는 방식입니다. 카드를 손에 들고 순서대로 정리하는 상황을 떠올리면 이해하기 쉽습니다.

정렬 전: 5 2 8 1 3

5는 정렬된 상태라고 가정
2를 5 앞에 삽입 → 2 5 8 1 3
8은 그대로 → 2 5 8 1 3
1을 맨 앞에 삽입 → 1 2 5 8 3
3을 2와 5 사이에 삽입 → 1 2 3 5 8

삽입 정렬은 데이터가 거의 정렬되어 있을 때 비교적 효율적으로 동작할 수 있습니다.

삽입 정렬은 현재 값을 정렬된 구간의 알맞은 위치에 끼워 넣는 정렬입니다.

---

10. 삽입 정렬 Java 코드

삽입 정렬을 Java 코드로 작성하면 다음과 같습니다.

int[] arr = {5, 2, 8, 1, 3};

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

for (int num : arr) {
    System.out.print(num + " ");
}

출력 결과는 다음과 같습니다.

1 2 3 5 8

key보다 큰 값들을 오른쪽으로 밀고, 알맞은 위치에 key를 삽입합니다.

---

11. 세 가지 기본 정렬 비교

선택 정렬, 버블 정렬, 삽입 정렬은 입문 단계에서 자주 배우는 기본 정렬입니다. 세 정렬 모두 구현은 비교적 단순하지만, 데이터가 많아지면 효율은 좋지 않습니다.

정렬	핵심 방식	시간복잡도
선택 정렬	가장 작은 값을 찾아 앞으로 보냄	O(N²)
버블 정렬	인접한 값을 비교하며 큰 값을 뒤로 보냄	O(N²)
삽입 정렬	정렬된 구간에 현재 값을 삽입	O(N²)

이 정렬들은 원리를 이해하기에는 좋지만, 실전 알고리즘 문제에서는 보통 Java 내장 정렬을 사용하는 경우가 많습니다.

---

12. O(N²) 정렬이 느린 이유

기본 정렬 알고리즘은 대부분 이중 반복문을 사용합니다. 그래서 시간복잡도가 O(N²)입니다.

N = 100       → 약 10,000번
N = 1,000     → 약 1,000,000번
N = 100,000   → 약 10,000,000,000번

N이 작을 때는 괜찮을 수 있지만, N이 커지면 O(N²) 정렬은 시간 초과가 발생할 가능성이 큽니다.

그래서 입력 크기가 큰 문제에서는 O(N log N) 정렬을 사용해야 합니다. Java의 Arrays.sort()나 Collections.sort()는 보통 이런 효율적인 정렬을 제공합니다.

입력 크기가 크다면 직접 구현한 O(N²) 정렬보다 내장 정렬을 사용하는 것이 안전합니다.

---

13. 안정 정렬과 불안정 정렬

정렬에는 안정 정렬과 불안정 정렬이라는 개념도 있습니다.

구분	의미
안정 정렬	값이 같은 데이터의 기존 순서를 유지함
불안정 정렬	값이 같은 데이터의 기존 순서가 바뀔 수 있음

예를 들어 점수가 같은 학생이 여러 명 있을 때, 원래 입력 순서를 유지해야 한다면 안정 정렬 여부가 중요할 수 있습니다.

정렬 전:
Kim 90
Lee 80
Park 90

점수 내림차순 정렬 후:
Kim 90
Park 90
Lee 80

Kim과 Park의 기존 순서가 유지되면 안정 정렬

입문 단계에서는 우선 오름차순과 내림차순, 시간복잡도부터 익히면 됩니다. 안정 정렬은 여러 조건 정렬을 다룰 때 더 중요해집니다.

---

14. 정렬이 사용되는 대표 문제 유형

정렬은 단독 문제뿐 아니라 여러 알고리즘의 준비 과정으로도 자주 사용됩니다.

문제 유형	정렬을 사용하는 이유
중복 제거	같은 값이 인접하게 모임
이분 탐색	정렬된 데이터가 필요함
투 포인터	양쪽 끝에서 조건을 조정하기 쉬움
그리디	작은 값 또는 큰 값부터 선택하기 쉬움
순위 계산	값의 순서를 기준으로 등수를 정할 수 있음

문제를 보다가 “작은 것부터”, “큰 것부터”, “순서대로”, “가장 먼저” 같은 표현이 보이면 정렬을 고려해볼 수 있습니다.

---

15. 정렬에서 자주 하는 실수

정렬 문제를 풀 때는 아래 실수를 자주 합니다.

• 오름차순과 내림차순을 반대로 이해하는 경우
• 입력 크기가 큰데 O(N²) 정렬을 직접 구현하는 경우
• 정렬 후 원래 인덱스가 필요하다는 점을 놓치는 경우
• 문자열 정렬에서 사전순 기준을 잘못 이해하는 경우
• 여러 조건 정렬에서 우선순위를 잘못 적용하는 경우
• 정렬이 필요한 문제인데 정렬 없이 탐색하는 경우
• 정렬하면 안 되는 문제에서 원본 순서를 바꿔버리는 경우

특히 원래 순서가 중요한 문제에서는 정렬을 하면 정보가 사라질 수 있습니다. 필요하다면 값과 원래 인덱스를 함께 저장해야 합니다.

값만 정렬하면 원래 위치를 잃을 수 있음
원래 위치가 필요하다면 값 + 인덱스를 함께 저장

정렬하기 전에 원래 순서가 필요한 문제인지 먼저 확인해야 합니다.

---

16. 정리

이번 글에서는 정렬 알고리즘 개념에 대해 정리했습니다.

• 정렬은 데이터를 특정 기준에 따라 순서대로 배치하는 작업이다.
• 오름차순은 작은 값에서 큰 값 순서, 내림차순은 큰 값에서 작은 값 순서이다.
• 선택 정렬은 가장 작은 값을 찾아 앞쪽으로 보내는 방식이다.
• 버블 정렬은 인접한 두 값을 비교하며 큰 값을 뒤로 보내는 방식이다.
• 삽입 정렬은 현재 값을 정렬된 구간의 알맞은 위치에 삽입하는 방식이다.
• 기본 정렬 알고리즘은 대부분 O(N²)이므로 입력이 크면 비효율적이다.
• 정렬은 이분 탐색, 투 포인터, 그리디 같은 알고리즘의 준비 과정으로 자주 사용된다.
• 정렬하기 전에 원래 순서가 필요한 문제인지 확인해야 한다.

정렬은 알고리즘 문제 풀이에서 정말 자주 사용되는 기본 도구입니다. 직접 정렬 알고리즘을 모두 구현할 일은 많지 않더라도, 정렬이 어떤 흐름으로 동작하고 왜 필요한지 이해하는 것은 매우 중요합니다.

정렬의 핵심은 데이터를 문제 해결에 유리한 순서로 재배치하는 것입니다.

---

다음 글 예고

다음 글에서는 Java 정렬 사용법에 대해 알아보겠습니다.

Arrays.sort(), Collections.sort(), 문자열 정렬, 내림차순 정렬, 객체 정렬의 기본 사용법을 예제로 정리해보겠습니다.