버블 정렬(Bubble Sort)

인접한 두 개의 원소를 비교하여 크기 순서대로 자리를 바꾸는 정렬 알고리즘

동작원리(오름차순 기준)

1. 배열의 첫 번째 원소부터 시작하여 바로 옆 원소와 크기를 비교
2. 앞의 값이 뒤의 값보다 크면 두 값의 위치를 서로 바꿈
3. 이 과정을 배열의 끝까지 반복
4. 마지막으로 이동한 값은 정렬이 완료된 것이므로 제외하고 나머지 구간에 대해 위 과정을 반복

구현 코드(C++)

#include <vector>

using namespace std;

void BubbleSort(vector<int>& arr)
{
    int n = arr.size();
		
    for (int i = 0; i < n - 1; ++i)
    {
        for (int j = 0; j < n - 1 - i; ++j)
        {
            if (arr[j] > arr[j + 1])
            {
		            // swap 함수로 대체 가능
		            // swap(arr[j], arr[j + 1])
                int temp = 0;

                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

장단점

• 장점
  • 구현이 매우 쉽고 직관적
• 단점
  • 데이터의 개수가 많아지면 비교 및 교환 횟수가 대폭 늘어나 속도가 매우 느림

성능표