[ 정렬 ] 버블정렬 (Bubble Sort) (C++)

이번 글에서는 Bubble Sorting에 대해서 다뤄보고자 한다.

버블정렬의 동작원리는 다음과 같다.

배열의 0번부터 N-1번까지 탐색을 하면서 인접한 칸과 비교하여 swap을 하는 방식이다.

아래의 그림이 버블정렬의 동작 원리이다.

위의 과정이 Bubble정렬을 1회 실시하고 나서의 결과이다.

본인은 오름차순으로 정렬한 과정을 표현하였는데, j번째 값과 j+1번째 값을 비교해서 만약 j번째의 값이 더 크다면

swap을 해주는 식으로 동작하는게 버블정렬이다.

위의 과정을 첫번째는 0 ~ N -1번까지, 두 번째는 0 ~ N -2번까지, 세 번째는 0 ~ N -3번까지... 식으로 진행되는데

이유는 위의 과정을 보면 알겠지만, 1회 실시하고 나게 되면 최댓값이 가장 마지막으로 가게 된다는 것을 알 수 있다.

즉, 2번째 과정에서는 이미 최댓값 위치에 저장되어있는 가장 마지막 값을 건드릴 필요가 없는 것이다.

# 시간복잡도

- 시간복잡도를 한번 계산해보자. 처음에는 N - 1번탐색, 두 번째는 N - 2번 탐색, 세 번째는.... 이런식으로 진행되므로

  총  N -1 + N - 2 + N - 3 + N - 4 + ... + 1 번을 진행하게 된다.

  이를 식으로 표현하게 되면 N(N-1)/2 가 된다.

  식의 유도는 하나의 예를 들어보면 쉽게 이해할 수 있다.

  1, 2, 3, 4, 5 가 존재할 때, 1회 탐색할때 총 1부터 5까지 4번 탐색을 하게된다.

  2회 탐색할 때에는 1부터 4까지 3번탐색, 3회는 2번, 4회는 1번... 총 4 + 3 + 2 + 1 = 10회 탐색을 하게된다.

  이 10을 식을 이용해서 도출해 내면 (5 x 4) / 2로 표현할 수 있게 된다. 따라서 위의 식 만큼의 탐색을 하게 된다.

  따라서 이라는 시간복잡도를 갖게 되고, 이를 빅오 표기법으로 표현하게 되면

  으로 표기할 수 있다.

  그렇다면 이제 최악의 경우와 최선의 경우를 한번 비교해보자.

  정렬에서 최악의 경우라고 하면 역방향으로 정렬이 되어 있는 경우일 것이다.

  예를  들어서 오름차순으로 정렬하려고 했는데 배열이 { 5, 4, 3, 2, 1 } 로 정렬되어 있는 경우이다.

  이 때의 시간복잡도는 어떻게 될까?? 직접 계산을 해보면 알겠지만, 똑같이 이 나오게 된다.

  최선의 경우는 어떻게 될까?? 최선의 경우는 아마 이미 정렬이 되어 있는 경우일 것이다.

  예를 들면 오름차순으로 정렬을 하고 싶을 때 { 1, 2, 3, 4, 5 } 로 정렬되어 있는 경우이다.

  이 경우에도 어차피 똑같은 탐색횟수를 가지게 된다.

  즉, Bubble정렬의 경우 최악이든 최선이든 똑같이 만큼의 시간복잡도를 갖게 된다.

[ 소스코드 ]

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<ctime>
 
#define MAX 100
using namespace std;
 
int Arr[MAX];
bool Flag[MAX];
 
void Print()
{
    cout << "################################################################################################" << endl;
    int Idx = 0;
    for (int i = 0; i < MAX; i++)
    {
        printf("%3d ", Arr[i]);
        Idx++;
        if (Idx == 20)
        {
            Idx = 0;
            cout << endl;
        }
    }
    cout << "################################################################################################" << endl;
}
 
void Bubble_Sort()
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX - i - 1; j++)
        {
            if (Arr[j] > Arr[j + 1])
            {
                swap(Arr[j], Arr[j + 1]);
            }
        }
    }
}
 
int main(void)
{
    srand((unsigned)time(NULL));
    for (int i = 0; i < MAX; )
    {
        Arr[i] = rand() % 300 + 1;
        if (Flag[Arr[i]] == false)
        {
            Flag[Arr[i]] = true;
            i++;
        }
    }
    cout << "[ Array State - Before Sorting ]" << endl;
    Print();
    cout << endl;
    Bubble_Sort();
    cout << "[ Array State - After Bubble Sorting ] " << endl;
    Print();
 
    return 0;
}