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

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

정렬 알고리즘

Bubble Sort — 가장 단순한 정렬

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

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

시간복잡도는 O(n²)입니다. 데이터가 1만 개만 넘어도 체감될 정도로 느려집니다. 교육용으로는 좋지만 실무에서 쓸 일은 거의 없습니다.

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²)입니다. Bubble Sort보다 swap 횟수는 적지만 비교 횟수는 동일합니다.

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²)이지만, 랜덤 피벗 선택으로 거의 발생하지 않습니다. C++ STL의 std::sort도 내부적으로 Introsort(Quick Sort 변형)를 사용합니다.

시간복잡도 비교

알고리즘	최선	평균	최악	안정성
Bubble Sort	O(n)	O(n²)	O(n²)	안정
Selection Sort	O(n²)	O(n²)	O(n²)	불안정
Quick Sort	O(n log n)	O(n log n)	O(n²)	불안정
Merge Sort	O(n log n)	O(n log n)	O(n log 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가 기본입니다.

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