버블 정렬

첫 번째 접근법은 다음과 같습니다. 배열의 길이를 $n$이라 하고, 배열을 왼쪽에서 오른쪽으로 $n$번 훑으면서 인접한 두 원소 중 앞의 것이 뒤의 것보다 크면 두 원소를 서로 바꿉니다.

매 반복마다 최댓값 원소가 거품처럼 배열의 끝으로 “떠오르며”, 이름도 여기서 유래했습니다.

void bubble_sort(int *a, int n) {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n - 1; i++)
            // сравниваем элемент со следующим
            if (a[i] > a[i + 1])
                // меняем местами, если следующий меньше
                swap(a[i], a[i + 1]);
}

int a[5] = {5, 2, 1, 3, 1};

bubble_sort(a, 5);

for (int i = 0; i < 5; i++)
    cout << a[i] << " ";

정확성. 귀납법으로 버블 정렬 알고리즘의 $k$단계가 끝난 뒤에는 마지막 $k$개의 수가 항상 정렬되어 있음을 보일 수 있으며, 따라서 알고리즘은 올바르게 동작합니다.

점근 복잡도. 두 개의 중첩 반복문이 있고, 각 반복문은 최대 $O(n)$번 반복하며, 그 안에서 $O(1)$ 시간에 비교와 swap이 일어나므로, 전체 실행 시간은 최대 $O(n^2)$입니다.

연습 문제. 이 알고리즘은 (점근적이지는 않지만) 조금 더 빠르게 만들 수 있습니다. 불필요한 동작을 전혀 하지 않으려면 두 for 반복문의 경계를 어떻게 바꿔야 합니까?