[멀티캠퍼스] 풀스택 개발자 아카데미 (14) - Algorithm(3)

목차 보기

0. 정렬 알고리즘
1. 완전 탐색 아이디어 접근
- 1.1. 버블 정렬 (Bubble Sort) 알고리즘
- 1.2. 선택 정렬 (Selection Sort) 알고리즘
2. 분할 정복 알고리즘
- 2.1. 병합 정렬 (Merge Sort)
- 2.2. 퀵 정렬 (Quick Sort)
3. 결론

시리즈·멀티캠퍼스 JAVA 풀스택 개발자 아카데미 6회차(30개의 글)

···
13.[멀티캠퍼스] 풀스택 개발자 아카데미 (13) - Algorithm(2)
14.[멀티캠퍼스] 풀스택 개발자 아카데미 (14) - Algorithm(3)현재
15.[멀티캠퍼스] 풀스택 개발자 아카데미 (15) - Algorithm(4)
···

0. 정렬 알고리즘

이전 글에서는 데이터를 순회하고 "탐색"하는 알고리즘에 대한 내용이었다.

이번 정렬 알고리즘은 데이터를 특정 순서로 나열하는, 컴퓨터 과학에서 가장 기본적이면서도 중요한 작업 중 하나이다.

효율적인 정렬은 이후의 데이터 검색이나 처리 속도를 극적으로 향상시키는 기반이 되기 때문에, 매우 유용한 알고리즘 중 하나이다.

이번 글에서는 저번 글의 '가능한 모든 경우를 시도하는' Brute-Force 전략의 아이디어가 어떻게 가장 단순한 정렬 알고리즘으로 이어지는지,

또 그 명확한 한계를 뛰어넘기 위해 어떻게 패러다임을 전환하는지, 즉, 분할 정복이라는 강력한 전략을 통해 O(n²)을 넘어, O(n log n)의 효율성을 달성하는 방법을 알아본다.

1. 완전 탐색 아이디어 접근

가장 직관적인 정렬 알고리즘은 '완전 탐색'의 아이디어를 공유한다. 즉, 각 요소를 다를 거의 모든 요소와 비교하고 자리를 바꾸는 과정을 반복하는 방법이다. 이 과정에서 이중 반복문이 필수적으로 사용되며, 이 때문에 해당 아이디어의 정렬 알고리즘이 O(n²)의 시간 복잡도를 갖는 근본적 원인이다.

Note

여기서 O(n²)은 입력받은 n개의 데이터에 대해 연산시간(연산횟수)가 n²에 비례하여 증가한다는 뜻이다. 즉, 데이터가 2개 증가하면 연산 시간(횟수)는 약 4배, 데이터가 10배 증가하면 연산 시간(횟수)는 100배로 증가한다.

1.1. 버블 정렬 (Bubble Sort) 알고리즘

버블 정렬은 정렬 알고리즘을 공부할 때 가장 먼저 접하는 알고리즘 중 하나로 꼽힐 정도로, 가장 직관적이며 단순한 알고리즘이다.

이 알고리즘은 한 번의 순회(Cycle)가 끝날 때마다, 가장 마지막에 올 데이터가 거품처럼 배열의 끝으로 올라오는 특징을 가진다.

1.1.1. 동작 원리

버블 정렬은 처음부터 끝까지 인접한 두 개의 데이터를 비교하며, 정렬 순서에 맞지 않으면 자리를 바꾸는 단순한 동작을 반복한다. 이 과정을 리스트의 끝까지 반복하면, 가장 마지막에 올 데이터가 리스트의 가장 끝에 위치하게 된다.

예를 들어, [4,1,3,5,2] 배열을 오름차순 정렬을 한다고 가정해보자.

1단계: [4,1,3,5,2]
1. 4와 1을 비교, 1이 더 작으므로 자리 교체 -> [1,4,3,5,2]
2. 4와 3을 비교, 3이 더 작으므로 자리 교체 -> [1,3,4,5,2]
3. 4와 5를 비교, 순서 문제가 없으므로 유지 -> [1,3,4,5,2]
4. 5와 2를 비교, 2가 더 작으므로 자리 교체 -> [1,3,4,2,5]
- 1단계가 끝나면 가장 큰 수인 5가 마지막에 위치
2단계: [1,3,4,2,5]
1. 1과 3을 비교, 순서 문제가 없으므로 유지 -> [1,3,4,2,5]
2. 3과 4를 비교, 순서 문제가 없으므로 유지 -> [1,3,4,2,5]
3. 4와 2를 비교, 2가 더 작으므로 자리 교체 -> [1,3,2,4,5]
- 마지막의 5는 정렬된 상태이므로 비교하지 않음
- 2단계가 끝나면 2번쨰 큰수인 4가 마지막에서 2번째에 위치
3단계: [1,3,2,4,5]
1. 1과 3을 비교, 순서 문제가 없으므로 유지 -> [1,3,2,4,5]
2. 3과 2를 비교, 2가 더 작으므로 자리 교체 -> [1,2,3,4,5]
- 3번째 큰 수인 3이 제자리에 위치
- 버블 정렬은 특별한 처리없이는 현재 정렬이 끝났는지 알 수 없으므로 끝까지 진행
4단계: [1,2,3,4,5]
1. 1과 2를 비교, 순서 문제가 없으므로 유지 -> [1,2,3,4,5]
- 종료

Java 구현

java

public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        // 각 순회마다 마지막 요소는 정렬되므로 비교 범위에서 제외
        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;
            }
        }
    }
}

1.2. 선택 정렬 (Selection Sort) 알고리즘

선택 정렬은 브루트 포스의 '완전 탐색' 개념과 더욱 닮아있다. "정렬되지 않은 부분에서 최솟값(또는 최댓값)을 '완전 탐색'하여 찾은 뒤, 정렬되지 않은 부분의 가장 앞에 있는 요소와 자리를 바꾸는" 과정을 반복한다는 아이디어이다.

1.2.1. 동작 원리

예를 들어, [4,1,3,5,2] 배열을 오름차순 정렬을 한다고 가정해보자.

1회전: [4,1,3,5,2] 전체에서 최솟값 1을 찾는다. 이후 첫 번째 요소 4와 자리를 바꾼다. -> [1,4,3,5,2]
2회전: [4,3,5,2] 부분에서 최솟값 2를 찾는다. 이후 두 번째 요소 4와 자리를 바꾼다. -> [1,2,3,5,4]
3회전: [3,5,4] 부분에서 최솟값 3를 찾는다. 3번째 자리에 위치 중(변화 없음) -> [1,2,3,5,4]
4회전: [5,4] 부분에서 최솟값 4를 찾는다. 4번쨰 요소 5와 자리를 바꾼다. -> [1,2,3,4,5]

Java 구현

java

public 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++) {
            // 최솟값의 index 탐색
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 최솟값을 정렬되지 않은 부분의 맨 앞으로 이동
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

2. 분할 정복 알고리즘

위와 같은 O(n²) 복잡도를 가진 완전 탐색법의 아이디어를 사용한 정렬 알고리즘은 데이터가 수만 개만 되어도 성능이 급격히 저하되어 사용할 수 없게 된다.

이러한 한계를 극복하기 위한 알고리즘이 분할정복 (Divide and Conquer)이다. 이는 한 번에 해결하기 어려운 문제를 해결 가능한 작은 문제들로 나눈 뒤, 그 해답들을 다시 합쳐 원래 문제의 답을 얻어내는 강력한 접근법이다.

이 전략이 강력한 이유는 문제의 복잡도를 선형적으로 줄이는 것이 아니라, 기하급수적으로 줄이기 때문이다. 100개의 데이터를 처리하는 문제에 대해, 99개와 1개로 나누는 것과, 50개와 50개로 나누는 것은 차원이 다르다. 후자의 경우, 문제의 크기를 절반으로 줄여나가기 때문에, 처리해야 할 연산의 총량을 극적으로 감소시킬 수 있다.

왜 O(n log n)인가?
- log n (분할): 배열을 계속해서 '절반'으로 나누면, 그 깊이는 log n이 된다. (8 -> 4 -> 2 -> 1, 3단계 = log₂8)
- n (정복 및 병합): 각 깊이(레벨)에서, 모든 n개의 원소에 대한 비교 및 통합 작업이 한 번씩 수행된다.
- 결론적으로 log n 단계에 걸쳐, 각 단계마다 n번의 작업을 수행하므로 시간 복잡도는O(n log n) 로 계산된다.

2.1. 병합 정렬 (Merge Sort)

병합 정렬은 분할 정복 패러다임의 교과서적인 예시이다. 어떠한 상황에서도 O(n log n)의 안정적인 성능을 보장하는 매우 신뢰도 높은 정렬 알고리즘이다.

또한 '선 분할, 후 정렬'의 대표주자로, 배열을 최소 단위(원소 1개)까지 쪼갠 뒤, 다시 합치는(Merge) 과정에서 정렬을 수행하는 방법이다. 이를 다른 말로 Top-down(위에서 아래로) 방식이라고 한다.

2.1.1. 동작 과정

분할: 배열이 1개가 될 때까지 재귀적으로 반으로 나눈다.
정복 및 병합: 두 개의 정렬된 부분 배열을 하나의 정렬된 배열로 병합한다. 이때 두 배열의 첫 요소부터 비교하며 더 작은 값을 새 배열에 추가하는 방식으로 진행된다.

Java 구현

java

// 병합 정렬을 수행하는 메인 메서드
public void sort(int[] arr, int left, int right) {
    if (left < right) {
        // 배열의 중간 지점을 계산
        int mid = (left + right) / 2;

        // 재귀적으로 왼쪽 절반과 오른쪽 절반을 정렬
        sort(arr, left, mid);
        sort(arr, mid + 1, right);

        // 정렬된 두 부분을 병합
        merge(arr, left, mid, right);
    }
}

// 두 개의 부분 배열을 병합하는 메서드
private void merge(int[] arr, int left, int mid, int right) {
    // 임시 배열의 크기를 지정
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 임시 배열을 생성
    int[] lArr = new int[n1];
    int[] rArr = new int[n2];

    // 데이터를 임시 배열로 복사
    for (int i = 0; i < n1; ++i) {
        lArr[i] = arr[left + i];
    }
    for (int j = 0; j < n2; ++j) {
        rArr[j] = arr[mid + 1 + j];
    }

    // --- 병합 과정 ---
    int i = 0, j = 0;
    int k = left; // 원래 배열(arr)의 시작 인덱스

    // lArr과 rArr 배열을 비교하며 작은 값을 원래 배열에 순서대로 적재
    while (i < n1 && j < n2) {
        if (lArr[i] <= rArr[j]) {
            arr[k] = lArr[i];
            i++;
        } else {
            arr[k] = rArr[j];
            j++;
        }
        k++;
    }

    // lArr이나 rArr에 남아있는 요소들을 원래 배열에 복사
    while (i < n1) {
        arr[k] = lArr[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = rArr[j];
        j++;
        k++;
    }
}

특징: 병합 정렬은 안정 정렬(Stable Sort)이며, 항상 O(n log n)을 보장하는 안정성이 최대 장점이지만, 정렬을 위한 추가적인 임시 배열(메모리)이 필요하다는 단점이 있다.

2.2. 퀵 정렬 (Quick Sort)

퀵 정렬은 '분할' 작업을 통해 실질적인 '정렬'이 이루어지는 독특한 알고리이다. 배열 내에서 기준점인 **피벗(Pivot)**을 정하고, 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누는 분할(Partition) 작업을 통해 정렬을 진행한다. 이 과정은 전체 배열에서 시작해 더이상 나눌 수 없을 때까지 작은 부분 배열로 파고드는 Top-down 방식이다.

이 알고리즘은 배열 내에서 기준점인 **피벗(Pivot)**을 정하고, 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누는 분할(Partition) 작업을 통해 정렬을 진행한다.

2.2.1. 동작 과정

이번 글에서는 **Lomuto 분할 방식(Lomuto Partition Scheme)**을 사용하며, 여러 피벗 선택 방법 중 배열의 가장 오른쪽 요소를 피벗으로 선택한다.

2.2.1.1. 1단계: partition 메서드 (분할)

partition 메서드의 목표는 피벗을 제자리에 위치시키고, 피벗을 기준으로 왼쪽에는 피벗보다 작은 값, 오른쪽에는 피벗보다 큰 값이 오도록 배열을 재배치하는 것이다.

피벗(Pivot) 선택: partition이 호출되면, 인자로 받은 배열의 범위 (low ~ high)의 가장 우측 값(arr[high])을 피벗으로 선택한다.
포인터 초기화:

i: 피벗보다 작거나 같은 값들이 위치하는 영역의 마지막 인덱스를 가리킨다. low-1로 초기화되며, 처음에는 아무런 값도 없음을 의미한다.
j: 현재 탐색 중인 원소를 가리킨다. low에서 시작하여 피벗 바로 앞(high-1)까지 배열을 순회한다. 즉, high에 도달하면 탐색을 종료한다.

배열 탐색 및 교환(Swap): for 루프를통해 j가 low 부터 high-1까지 이동하며 다음을 반복한다.

만약 arr[j](현재 값)이 피벗보다 작거나 같으면:
1. i를 1증가 시킨다(i가 다음 위치로 이동)
2. arr[i]와 arr[j]의 위치는 교환(Swap) 한다.
3. 해당 과정을 통해 i를 포함한 왼쪽 영역은 항상 피벗보다 작거나 같은 값이 남는다.
만약 arr[j](현재 값)이 피벗보다 크면, j만 증가시키고 아무런 작업을 하지 않는다.

피벗 위치 확정: 루프가 종료되면, low부터 i까지는 피벗보다 작거나 같은 값들이, 피벗을 제외한 i+1부터 j까지는 피벗보다 큰 값이 남게 된다. 이제 피벗을 제자리로 옯기기 위해 arr[i+1](i 다음 위치)와 arr[high](피벗)의 위치를 교환한다.
피벗 인덱스 반환: 이 교환을 통해, 피벗을 정렬된 배열에서의 자신의 위치를 찾게 된다. 이제, partition은 피벗의 위치를 반환하여 피벗의 좌측과 우측을 정렬할 수 있도록 한다.

2.2.1.2. 2단계: sort 메서드

sort 메서드는 partition을 이용해 정체 정렬을 관리하고 실행한다.

종료 조건 확인: 먼저, 넘겨받은 인자 중, low < high 인지 확인한다. 만약 low가 high보다 크거나 같은 경우, 배열에 원소가 없거나 하나만 있다는 뜻으로, 별다른 작업 없이 재귀를 종료한다.
분할 실행: partition(arr, low, high)를 호출해 피벗을 올바른 위치에 놓고, 피벗의 위치(pi)를 받는다.
하위 배열 정렬:

sort(arr, low, pi-1): 피벗을 기준으로 나뉜 왼쪽 부분 배열에 대해 다시 sort 메서드를 재귀 호출한다.
sort(arr, pi+1, high): 마찬가지로, 오른쪽 부분 배열에 대해 sort 메서드를 재귀 호출한다.

이러한 재귀 호출이 더이상 분할 할 수 없는 부분 배열(크기가 1 이하)에 도달할 때까지 반복되면, 전체 배열의 정렬이 완료된다.

2.2.2. 실습

Java 구현

java

// 퀵 정렬을 수행하는 메인 메서드
public void sort(int[] arr, int low, int high) {
    if (low < high) {
        // 분할(partition) 후 피벗의 위치 획득
        int pi = partition(arr, low, high);

        // 피벗을 기준으로 왼쪽과 오른쪽 부분 배열에 대해 재귀적으로 정렬
        sort(arr, low, pi - 1);
        sort(arr, pi + 1, high);
    }
}

// 배열을 분할하고 피벗의 최종 위치를 반환하는 메서드
private 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++;
            // arr[i]와 arr[j]를 교환
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // 피벗을 올바른 위치로 이동 (i + 1)
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;
}

특징: 퀵 정렬은 평균적으로 매우 빠른 속도(O(n log n))와 추가 메모리가 거의 필요 없는 '제자리 정렬'이라는 장점 때문에 실무에서 널리 쓰인다. 하지만 불안정 정렬(Unstable Sort)이며, 피벗 선택이 최악일 경우(예: 이미 정렬된 배열에서 첫 요소를 피벗으로 선택), O(n²)까지 성능이 저하될 수 있다.

3. 결론

지금까지 정렬이라는 하나의 목표를 위해 서로 다른 두 가지 접근법을 비교했다.

O(n²) 정렬 (버블, 선택): Brute-Force처럼 직관적이고 구현이 쉽지만, 데이터가 많아지면 실용성이 떨어진다. 알고리즘의 기본 원리를 이해하는 데 큰 도움이 된다.
O(n log n) 정렬 (병합, 퀵): 분할 정복이라는 세련된 패러다임을 통해 비교 횟수를 혁신적으로 줄여 대용량 데이터도 효율적으로 처리한다.

개발자에게 중요한 것은 단순히 코드를 암기하는 것이 아니라, 각 알고리즘의 근간이 되는 패러다임을 이해하는 것이다. 문제의 크기와 특성을 파악하고, 그에 맞는 최적의 도구(알고리즘)를 선택하는 능력이야말로 진정한 문제 해결 능력의 핵심이다.