알고리즘 입문: 정렬과 탐색

코딩 테스트 준비든 실무 개발이든, 정렬과 탐색은 피할 수 없는 기본기입니다. 어떤 언어를 쓰든 결국 이 두 가지로 귀결되는 문제가 대부분입니다.

정렬 알고리즘

Bubble Sort — 가장 단순한 정렬

인접한 두 원소를 비교해서 순서가 틀리면 교환합니다. 직관적이지만 느립니다.

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;  // 한 바퀴 동안 교환이 없으면 이미 정렬된 상태
    }
}

평균과 최악의 시간복잡도는 O(n²)입니다. 데이터가 1만 개만 넘어도 체감될 정도로 느려집니다. swapped 플래그 덕분에 이미 정렬된 배열은 한 바퀴만 훑고 끝나서, 최선의 경우는 O(n)입니다. 플래그가 없으면 정렬된 입력도 끝까지 다 돌아 항상 O(n²)입니다. 교육용으로는 좋지만 실무에서 쓸 일은 거의 없습니다.

Selection Sort — 최솟값 찾기 반복

전체 배열에서 최솟값을 찾아 맨 앞으로 보내는 방식입니다.

void selectionSort(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;
            }
        }
        std::swap(arr[i], arr[minIdx]);
    }
}

이것도 O(n²)입니다. swap은 많아야 n-1번이라 Bubble Sort보다 적지만, 비교는 입력과 상관없이 항상 n(n-1)/2번이라 정렬된 배열을 넣어도 빨라지지 않습니다.

Quick Sort — 실전에서 가장 많이 쓰이는 정렬

피벗을 기준으로 작은 값과 큰 값을 나누고, 재귀적으로 정렬합니다.

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++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

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

평균 시간복잡도 O(n log n). 다만 이 코드는 마지막 원소를 피벗으로 고정해서, 이미 정렬됐거나 거꾸로 정렬된 배열, 모든 값이 같은 배열에서는 매번 한쪽으로만 나뉘어 O(n²)이 됩니다. 재귀 깊이도 n까지 깊어집니다.

피벗을 무작위로 고르거나, 처음·중간·끝 세 값의 중앙값(median-of-three)을 피벗으로 쓰면 이런 입력에서 최악을 피하기 쉬워집니다. C++ STL의 std::sort도 내부적으로 Introsort(Quick Sort 변형)를 사용합니다.

Merge Sort: 반으로 나눠 정렬한 뒤 합치기

배열을 반으로 계속 나눈 다음, 정렬된 두 조각을 앞에서부터 비교하며 하나로 합칩니다.

void merge(int arr[], int left, int mid, int right) {
    std::vector<int> tmp;
    tmp.reserve(right - left + 1);
    int i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) tmp.push_back(arr[i++]);  // 같으면 왼쪽 먼저 → 안정 정렬
        else tmp.push_back(arr[j++]);
    }
    while (i <= mid) tmp.push_back(arr[i++]);
    while (j <= right) tmp.push_back(arr[j++]);
    for (int k = 0; k < (int)tmp.size(); k++) arr[left + k] = tmp[k];
}

void mergeSort(int arr[], int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

나누는 단계가 log n번이고 단계마다 합치는 일이 n번이라, 입력이 어떻든 O(n log n)입니다. Quick Sort처럼 입력에 따라 느려지는 경우가 없습니다. 대신 합칠 때 임시 배열 tmp가 필요해서 메모리를 O(n) 더 씁니다. 합칠 때 <=를 써서 같은 값이면 왼쪽 원소를 먼저 넣기 때문에 안정 정렬입니다.

시간복잡도 비교

"안정 정렬"이란 같은 값의 원소들이 원래 순서를 유지하는 것입니다. 데이터에 부가 정보가 있을 때 중요해집니다.

탐색 알고리즘

Linear Search — 하나씩 확인

배열을 처음부터 끝까지 순회하면서 목표 값을 찾습니다. 정렬이 필요 없다는 장점이 있습니다.

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

O(n)입니다. 데이터가 적거나 정렬되지 않은 경우에 씁니다.

Binary Search — 반씩 잘라내기

정렬된 배열에서만 동작합니다. 중간값과 비교해서 절반을 버리는 방식이라 매우 빠릅니다.

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

O(log n)입니다. 100만 개의 데이터에서 최대 20번의 비교로 답을 찾습니다.

mid = (left + right) / 2 대신 mid = left + (right - left) / 2를 쓰는 이유는 정수 오버플로우 방지입니다. 사소해 보이지만 실제 코딩 테스트에서 이 차이로 틀리는 경우가 있습니다.

어떤 상황에 어떤 알고리즘을 쓸까

정렬이 필요하면 대부분의 경우 std::sort를 쓰면 됩니다. 직접 구현할 일은 코딩 테스트 외에는 드뭅니다. 탐색은 데이터가 정렬되어 있으면 Binary Search, 아니면 Linear Search가 기본입니다.

직접 각 알고리즘을 구현해보고, 데이터 크기를 바꿔가며 실행 시간을 측정해 보는 것을 권합니다. 숫자로 체감해야 시간복잡도가 몸에 익습니다.