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

안녕하세요! 이번 강좌에서는 C++를 사용하여 버블 소트(Bubble Sort) 알고리즘을 구현하는 방법에 대해 알아보겠습니다. 버블 소트는 단순하면서도 이해하기 쉬운 정렬 알고리즘으로, 주로 교육용으로 사용됩니다. 이 글에서는 버블 소트의 기본 개념, 시간 복잡도, 그리고 실제 구현을 단계별로 설명할 것입니다.

버블 소트 알고리즘의 개요

버블 소트는 인접한 두 요소를 비교하여 정렬하는 방법입니다. 이 과정은 리스트의 모든 요소가 정렬될 때까지 반복됩니다. 버블 소트의 이름은 가장 큰 값이 가장 뒤로 ‘버블’처럼 올라가기 때문입니다.

버블 소트 알고리즘의 동작 방식

  1. 리스트의 첫 번째 요소와 두 번째 요소를 비교합니다.
  2. 첫 번째 요소가 두 번째 요소보다 크면 두 요소의 위치를 교환합니다.
  3. 리스트의 끝까지 이 과정을 반복합니다. 이 과정의 한 사이클을 ‘패스(pass)’라고 합니다.
  4. 정렬이 완료될 때까지 1번에서 3번까지의 과정을 반복합니다.

시간 복잡도

버블 소트의 시간 복잡도는 최악의 경우O(n^2)입니다. 이는 리스트의 모든 요소를 한 번씩 비교해야 하기 때문입니다. 최선의 경우(이미 정렬된 경우)도 O(n)입니다. 이러한 이유로 버블 소트는 대규모 데이터 정렬에는 비효율적입니다.

알고리즘 구현

이제 C++ 코드를 통해 버블 소트를 구현해 보겠습니다. 먼저 기본적인 버블 소트 코드를 살펴보고 각 부분을 설명하겠습니다.

#include <iostream>
using namespace std;

// 버블 소트 함수
void bubbleSort(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]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

// 배열 출력 함수
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 메인 함수
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "정렬 전 배열: ";
    printArray(arr, n);
    
    bubbleSort(arr, n);
    
    cout << "정렬 후 배열: ";
    printArray(arr, n);
    return 0;
}

코드 설명

  • #include <iostream>: 표준 입력과 출력을 위한 헤더 파일입니다.
  • swap(arr[j], arr[j + 1]): 현재 요소와 다음 요소를 교환하기 위한 C++의 내장 함수인 swap을 사용합니다.
  • printArray 함수: 주어진 배열을 출력하는 함수입니다.
  • main 함수: 프로그램의 시작 지점으로, 배열 초기화 및 정렬 호출이 이루어집니다.

실행 결과

위 코드를 실행하면 아래와 같은 결과를 얻습니다:

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

정렬 전 배열과 정렬 후 배열을 비교하면 버블 소트가 제대로 작동하고 있음을 확인할 수 있습니다.

버블 소트의 개선 방안

기본 버블 소트 구현은 불필요한 비교를 포함하고 있습니다. 만약 패스 중에 교환이 발생하지 않으면 이미 정렬된 상태이므로, 추가적인 패스를 수행할 필요가 없습니다. 이를 통해 알고리즘의 효율성을 높일 수 있습니다.

void improvedBubbleSort(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true; // 교환이 일어났음을 기록
            }
        }
        if (!swapped) break; // 더 이상 교환이 없으면 반복 종료
    }
}

결론

이번 강좌에서는 C++로 버블 소트를 구현하는 방법에 대해 알아보았습니다. 버블 소트는 간단한 알고리즘이지만, 실무에서는 성능이 좋지 않기 때문에 더 효율적인 알고리즘이 요구됩니다. 그래도 버블 소트는 교육적인 가치가 크기 때문에 언급할 가치가 있습니다.

앞으로도 C++ 알고리즘 강좌를 지속적으로 제공할 예정이므로 많은 관심 부탁드립니다! 질문이나 의견이 있다면 댓글로 남겨주세요!