[Algorithm] 버블 정렬 (Bubble Sort)

Bubble Sort

• 이웃하는 값과 비교해 특정 수(최대 or 최소)를 한 쪽(앞 or 뒤)로 이동시키는 과정을 반복

 

코드

#include <iostream>

void Print(int* arr)
{
    for (int i = 0; i < 10; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << "\n";
}

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

int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(0);

    int arr[10] = {8, 31, 48, 73, 3, 65, 20, 29, 11, 15};

    Print(arr);
    BubbleSort(arr);
    Print(arr);
}

시간 복잡도

평균과 최악 모두 O(n^2)의 시간 복잡도를 가진다.

참고사항

• 교환이 많아 비효율적이라 실전용 알고리즘은 아니다.
• 바깥 루프를 한 번 돌 때마다 원소 하나의 위치가 확정된다.