C++ 코딩테스트 강좌, 버블 소트 프로그램 1

이번 강좌에서는 C++을 이용해 버블 소트(Bubble Sort) 알고리즘을 구현하는 방법을 다루겠습니다. 버블 소트는 가장 간단한 정렬 알고리즘 중 하나로, 인접한 두 요소를 비교하여 큰 요소를 뒤로 보내는 방식으로 정렬합니다. 이 알고리즘을 통해 정렬 알고리즘의 기초를 이해하고, C++에서의 구현 방식을 익히는 데 중점을 둘 것입니다.

문제 정의

주어진 정수 배열을 오름차순으로 정렬하는 프로그램을 작성하세요.

입력

입력은 여러 개의 정수로 구성된 배열입니다. 예를 들어, 다음과 같은 배열이 주어진다고 가정합시다:
[64, 34, 25, 12, 22, 11, 90]

출력

배열이 오름차순으로 정렬된 결과를 출력합니다. 예를 들어, 위의 입력에 대한 출력은 다음과 같습니다:
[11, 12, 22, 25, 34, 64, 90]

버블 소트(Bubble Sort) 알고리즘

버블 소트의 기본 아이디어는 인접한 두 원소를 비교하여 정렬하는 것입니다. 만약 첫 번째 원소가 두 번째 원소보다 크다면, 두 원소를 교환합니다. 이 과정을 배열의 끝까지 반복하며, 각 반복이 끝날 때마다 가장 큰 원소가 마지막 위치로 이동하게 됩니다. 아래는 버블 소트 알고리즘을 설명하는 간단한 단계입니다:

배열의 첫 번째 원소부터 시작해 인접한 두 원소를 비교합니다.
만약 첫 번째 원소가 두 번째 원소보다 크다면 두 원소를 교환합니다.
이 과정을 배열 끝까지 반복합니다.
이 과정을 배열 길이 – 1 만큼 반복하여, 이미 정렬된 구간이 생기는 경우 반복을 조기 종료할 수 있습니다.

C++ 코드 구현

이제 C++를 사용하여 버블 소트를 구현해 보겠습니다. 아래는 버블 소트를 구현한 C++ 코드입니다:

 
#include <iostream>
#include <vector>

using namespace std;

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    bool swapped;
    
    // 배열의 모든 원소를 반복
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        // 마지막 i개 원소는 이미 정렬되었으므로, n-i-1까지 반복
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 두 원소 교환
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        // 만약 원소 교환이 없었다면, 배열이 이미 정렬되었으므로 종료
        if (!swapped) break;
    }
}

int main() {
    vector<int> data = {64, 34, 25, 12, 22, 11, 90};
    
    cout << "정렬 전 배열: ";
    for (int num : data) {
        cout << num << " ";
    }
    
    bubbleSort(data);
    
    cout << "\n정렬 후 배열: ";
    for (int num : data) {
        cout << num << " ";
    }
    
    return 0;
}

코드 설명

위의 코드는 C++에서 버블 소트를 구현한 간단한 예제입니다. 우선, vector 라이브러리를 사용하여 정수 배열을 선언하고 초기화합니다. bubbleSort 함수는 전달된 배열을 정렬하는 기능을 수행합니다.

int n = arr.size(); – 배열의 크기를 가져옵니다.
for (int i = 0; i < n - 1; i++) – 배열의 모든 원소를 순회합니다.
for (int j = 0; j < n - i - 1; j++) – 마지막 i개 원소는 이미 정렬되었으므로, 이 범위에서 비교합니다.
if (arr[j] > arr[j + 1]) – 두 원소가 순서대로 되어 있지 않으면, swap 함수를 사용하여 두 원소를 교환합니다.
if (!swapped) break; – 교환이 없었다면, 배열이 이미 정렬된 상태이므로 반복을 조기에 종료합니다.

테스트 및 결과 확인

이제 코드를 실행하여 결과를 확인해 보겠습니다. 위 코드를 실행했을 때의 출력은 다음과 같습니다:


정렬 전 배열: 64 34 25 12 22 11 90 
정렬 후 배열: 11 12 22 25 34 64 90

알고리즘 분석

버블 소트는 이해하기 쉬운 알고리즘이지만, 효율성 면에서는 문제가 있습니다. 최악의 경우와 평균 경우의 시간 복잡도는 O(n²)입니다. 이는 배열의 크기가 커질수록 성능이 크게 저하됨을 의미합니다. 이러한 이유로 버블 소트는 실무에서 사용되기보다는 교육적인 목적에 적합합니다.

시간 복잡도

최악의 경우: O(n²)
평균 경우: O(n²)
최선의 경우: O(n) (이미 정렬된 경우)

공간 복잡도

O(1) (주어진 배열을 직접 수정하므로)

버블 소 트의 장단점

장점

알고리즘이 간단하다.
입문자가 이해하기 쉽다.
자체적으로 정렬 유무를 판별할 수 있다.

단점

시간 복잡도가 높아 실제 응용에서 비효율적이다.
큰 데이터셋에서는 사용을 권장하지 않는다.

결론

이번 강좌에서 우리는 버블 소트를 통해 C++에서 정렬 알고리즘을 구현하는 방법을 배웠습니다. 버블 소트의 기초적인 개념과 알고리즘 구현을 통해 정렬의 기본 원리를 이해할 수 있었습니다. 앞으로 더 효율적인 정렬 알고리즘(예: 퀵 소트, 병합 정렬 등)에 대해 깊게 공부하시길 바랍니다.

이 글이 C++ 코딩테스트 준비에 도움이 되었다면 좋겠습니다. 추가적인 질문이나 더 배우고 싶은 알고리즘이 있다면 댓글로 남겨주세요!