왜 탐색·정렬을 다시 배우는가

04편에서 시간복잡도(Big-O)를 개념으로만 소개했다. 이 편은 그 개념을 실제 탐색·정렬 알고리즘의 반복 횟수를 직접 세어서 증명하는 자리다. 통합프로그래밍 시험에서는 “이 정렬 알고리즘의 1회전(패스) 후 배열 상태는?”, “이 알고리즘의 평균 시간복잡도는?”처럼 코드를 손으로 실행하고 그 결과로 복잡도를 판단하는 문제가 나온다. 즉 이 편의 목표는 “복잡도 표를 암기”가 아니라 왜 그 차수가 나오는지 반복문을 세어서 스스로 유도하는 것이다.

빅오 표기 복습: 반복 횟수를 세는 법

빅오(Big-O) 표기는 입력 크기 $n$이 커질 때 연산 횟수가 어떤 속도로 늘어나는지를 나타낸다. 반복문이 중첩된 만큼 곱해진다는 원칙만 정확히 이해하면 코드만 보고 복잡도를 유도할 수 있다.

for (int i = 0; i < n; i++) {      /* n번 반복 */
    for (int j = 0; j < n; j++) {  /* 바깥 1번마다 n번 반복 */
        /* 이 안의 연산은 총 n * n번 실행 */
    }
}

바깥 반복문이 $n$번 돌고, 그 각각에 대해 안쪽 반복문이 다시 $n$번 도니까 전체 실행 횟수는 $n \times n = n^2$번이다. 이를 $O(n^2)$이라고 쓴다.

• $n$: 입력 크기(예: 배열의 원소 개수)
• $O(n^2)$: 실행 횟수가 $n$의 제곱에 비례해 늘어난다는 뜻(제곱을 나타내는 이 표기를 “빅오 n 제곱”이라고 읽는다)

선형 탐색: 처음부터 끝까지 하나씩

선형 탐색(linear search)은 배열의 맨 앞부터 끝까지 순서대로 값을 하나씩 비교하는 가장 단순한 탐색이다.

int 선형탐색(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

배열 [5, 2, 8, 1, 9]에서 선형탐색(arr, 5, 1)을 호출했을 때 비교 과정을 추적한다.

최선의 경우(찾는 값이 맨 앞) 비교 1번, 최악의 경우(찾는 값이 맨 끝이거나 없음) 비교 $n$번이 필요하다. 그래서 선형 탐색의 시간복잡도는 최악·평균 모두 $O(n)$이다.

이진 탐색: 정렬된 배열을 절반씩 잘라내기

이진 탐색(binary search)은 배열이 정렬되어 있다는 전제 아래, 중간값과 비교해 찾는 값이 왼쪽 절반에 있는지 오른쪽 절반에 있는지를 판단하며 후보 범위를 절반씩 줄여 나간다. 14편에서 다룬 이진 탐색 트리(BST)의 탐색 원리와 정확히 같다.

int 이진탐색(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

정렬된 배열 [1, 3, 5, 7, 9, 11, 13](인덱스 0~6)에서 이진탐색(arr, 7, 11)을 호출했을 때를 추적한다.

7개 원소 중 단 2번의 비교로 값을 찾았다. 선형 탐색이었다면 최악의 경우 6번(인덱스 5까지) 비교해야 했다. 배열 크기가 두 배씩 늘어날 때마다 이진 탐색은 비교 횟수가 겨우 1번씩만 늘어나는데, 이 성질이 시간복잡도 $O(\log n)$의 정체다.

• $\log_2 n$: “$n$을 몇 번 반으로 나누어야 1이 되는가”를 뜻하는 로그(log) 계산. 밑(base)이 2인 이유는 매번 절반으로 자르기 때문이다.

자주 틀리는 점: “이진 탐색이 선형 탐색보다 항상 더 빠르다”는 조건 없이 외우면 틀린다. 이진 탐색은 정렬된 배열에서만 쓸 수 있다. 정렬되지 않은 배열이라면 먼저 정렬(아래에서 다룰 O(n log n) 이상의 비용)을 해야 하므로, 딱 한 번만 탐색할 거라면 선형 탐색이 더 유리할 수도 있다.

버블 정렬: 인접한 두 값을 계속 비교해 교환

버블 정렬(bubble sort)은 인접한 두 원소를 비교해 순서가 잘못되어 있으면 교환하는 과정을 배열 끝까지 반복하는 정렬이다. 한 번의 패스(pass, 배열을 한 번 훑는 것)가 끝나면 가장 큰 값이 거품처럼 맨 뒤로 떠오른다.

void 버블정렬(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

배열 [5, 2, 8, 1]을 버블 정렬로 정렬하는 과정을 패스별로 추적한다.

각 패스가 끝날 때마다 맨 뒤에 정렬된 값(1패스 후 8, 2패스 후 5·8)이 하나씩 확정된다는 점에 주목한다. $n$개 원소를 정렬하려면 최대 $n-1$번의 패스가 필요하고, 각 패스마다 최대 $n-1$번 비교하므로 전체 비교 횟수는 대략 $n \times n$번, 즉 $O(n^2)$이다.

선택 정렬: 최솟값을 찾아 맨 앞으로

선택 정렬(selection sort)은 매 회전마다 아직 정렬되지 않은 부분에서 최솟값을 찾아 그 부분의 맨 앞과 교환하는 방식이다.

void 선택정렬(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        int temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
    }
}

같은 배열 [5, 2, 8, 1]을 선택 정렬로 정렬하는 과정이다.

버블 정렬은 인접한 값을 매번 교환하지만, 선택 정렬은 한 회전에 교환이 최대 한 번만 일어난다는 점이 다르다. 다만 비교 횟수 자체는 버블 정렬과 마찬가지로 $O(n^2)$이다.

삽입 정렬: 이미 정렬된 부분에 카드를 끼워 넣듯

삽입 정렬(insertion sort)은 손에 든 카드를 정렬할 때처럼, 이미 정렬된 앞부분에 새 원소를 알맞은 위치에 끼워 넣는 방식이다. 13편에서 다룬 배열 리스트의 “중간 삽입 시 뒤에서부터 밀기”와 같은 동작을 정렬 전체에 반복 적용한다.

void 삽입정렬(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

배열 [5, 2, 8, 1]을 삽입 정렬로 정렬하는 과정이다.

삽입 정렬은 이미 거의 정렬된 배열에서는 밀어야 할 원소가 거의 없어 최선의 경우 $O(n)$까지 빨라진다는 점이 버블·선택 정렬과의 중요한 차이다. 반면 배열이 역순으로 정렬되어 있으면(최악의 경우) 매번 앞의 모든 원소를 밀어야 해 $O(n^2)$이 된다.

퀵 정렬: 기준값으로 나누어 정복

퀵 정렬(quick sort)은 배열에서 피벗(pivot, 기준값)을 하나 정하고, 피벗보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 몰아 배열을 둘로 나눈 뒤, 각 부분을 재귀적으로 같은 방식으로 정렬한다. 13편에서 배운 재귀가 실제 정렬 알고리즘에 쓰이는 대표 사례다.

int 분할(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 = i + 1;
            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;
}
 
void 퀵정렬(int arr[], int low, int high) {
    if (low < high) {
        int p = 분할(arr, low, high);
        퀵정렬(arr, low, p - 1);
        퀵정렬(arr, p + 1, high);
    }
}

배열 [5, 2, 8, 1]에서 맨 마지막 원소 1을 피벗으로 분할을 호출했을 때를 추적한다(low=0, high=3, pivot=1).

피벗(1)이 배열에서 가장 작은 값이라 왼쪽에 아무것도 옮기지 못하고 자기 자신이 맨 앞으로 이동했다. 이렇게 피벗이 항상 한쪽 끝에 치우쳐 뽑히는 경우(이미 정렬되었거나 역순인 배열에서 자주 발생)가 퀵 정렬의 최악의 경우이며, 이때는 매번 부분 배열이 1개씩만 줄어들어 $O(n^2)$까지 나빠진다. 반대로 피벗이 매번 배열을 절반씩 나누면 평균 $O(n \log n)$의 성능을 낸다.

시간복잡도 정리와 비교표

자주 틀리는 점: 버블·선택·삽입 정렬을 “다 O(n²)이니 성능이 똑같다”고 오해하기 쉽다. 최악의 경우 차수는 같지만, 최선의 경우(이미 정렬된 데이터)에서는 삽입 정렬만 O(n)으로 빨라진다. “어떤 상황(이미 정렬됨, 역순, 무작위)에서 어떤 알고리즘이 유리한가”를 묻는 문제는 이 차이를 정확히 알아야 풀 수 있다.

절차형 정렬과 객체지향 정렬 호출 방식 비교

같은 정렬 기능을 절차형(C)과 객체지향(Java)에서 어떻게 다르게 조직하는지 비교한다. 13편에서 스택을 비교했던 것과 같은 관점이다.

/* C: 정렬 대상 배열을 함수의 인자로 명시적으로 전달 */
void 버블정렬(int arr[], int n) { /* ... */ }
 
int main(void) {
    int arr[4] = {5, 2, 8, 1};
    버블정렬(arr, 4);
}

// Java: 배열을 객체로 감싼 클래스가 자기 자신을 정렬하는 메서드를 가진다
public class IntArraySorter {
    private int[] data;
 
    public IntArraySorter(int[] data) {
        this.data = data;
    }
 
    public void bubbleSort() {
        int n = data.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (data[j] > data[j + 1]) {
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
            }
        }
    }
}

핵심 정리

• 선형 탐색은 O(n), 이진 탐색은 정렬된 배열에서 O(log n)이며, 이진 탐색은 매 단계 후보 범위를 절반으로 줄인다.
• 버블·선택 정렬은 항상 O(n²), 삽입 정렬은 최선의 경우 O(n)까지 빨라질 수 있다.
• 퀵 정렬은 평균 O(n log n)이지만 피벗이 계속 한쪽으로 치우치면 최악 O(n²)까지 나빠진다.
• 시간복잡도는 반복문의 중첩 구조를 직접 세어서 유도할 수 있으며, 최선·평균·최악을 구분해 판단해야 한다.
• 같은 정렬 로직도 C는 배열과 함수를 분리해 호출하고, Java는 배열을 객체에 캡슐화해 메서드로 호출한다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제  — 4단계 통합프로그래밍의 평가영역과 출제 범위를 확인할 수 있는 공식 사이트.