C/C++ 알고리즘

버블 정렬

각 pass가 가장 큰 미정렬 값을 끝으로 보냅니다.

버블 정렬이란?

각 pass가 가장 큰 미정렬 값을 끝으로 보냅니다.

인접한 역순 요소를 교환해 정렬합니다.

중요한 점

빈 입력, 한 요소, 중복, 정렬된 입력을 테스트하세요.
정확성과 최적화를 분리하세요.
프로덕션에서는 standard library를 우선하세요.

버블 정렬 시각화

O(n²)

재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.

C와 C++ 코드 예제

실행 →

main.c

#include <stdio.h>

int main(void) {
    int values[] = {5, 1, 4, 2};
    for (int end = 3; end > 0; --end) {
        int changed = 0;
        for (int index = 0; index < end; ++index) {
            if (values[index] > values[index + 1]) {
                int temporary = values[index];
                values[index] = values[index + 1];
                values[index + 1] = temporary;
                changed = 1;
            }
        }
        if (!changed) break;
    }
    for (int index = 0; index < 4; ++index) {
        printf("%d ", values[index]);
    }
}

예상 출력

1 2 4 5

C++

실행 →

main.cpp

#include <iostream>
#include <vector>

int main() {
    std::vector values{5, 1, 4, 2};
    for (auto end = values.end(); end != values.begin(); --end) {
        bool changed = false;
        for (auto item = values.begin(); item + 1 != end; ++item) {
            if (*item > *(item + 1)) {
                std::iter_swap(item, item + 1);
                changed = true;
            }
        }
        if (!changed) break;
    }
    for (int value : values) {
        std::cout << value << ' ';
    }
}

예상 출력

1 2 4 5

C와 C++ 비교

교육용이며 O(n²)입니다. Early exit로 sorted input은 O(n), 실무 C++는 보통 std::sort를 씁니다.

Loop, pointer, length와 buffer가 명시적입니다.

C++

Iterator와 algorithm이 연산과 저장 방식을 분리합니다.

연습 문제

두 버전을 실행하고 수정하여 각 언어의 보장을 관찰하세요.

각 비교를 직접 추적하세요.
중복과 극값을 테스트하세요.
Standard library와 benchmark하세요.