버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)

버블 정렬은 모든 값들을 한번씩 비교를 하기 때문에 전체가 이미 정렬이 끝났는지 안끝났는지 미리 확인을 할 수 있다. 그래서 정렬 알고리즘 끼리도 항상 어떤 알고리즘이 좋다 라고 할순 없다.
경우에 따라 다르기 때문이다.

#include <iostream>

using namespace std;

void Print(int *arr, int size)
{
    for (int i = 0; i < size; i++)
    {
        cout << arr[i] << " " << flush;
    }
    cout << endl;
}

int main()
{
    int arr[] = { 5, 4, 3, 2, 1 };
    int size = sizeof(arr) / sizeof(int);

    for (int i = 0; i < size - 1; i++)
    {
        Print(arr, size);
        cout << endl;
        bool swapped = false;
        for (int j = 0; j < size - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
            Print(arr, size);
        }
        if (swapped == false)
        {
            break;
        }
    }
    return 0;
}

bool swapped = false;

boolean 변수를 이용하여 swap할게 없을때 loop를 단축시킬 수 있다.

for (int j = 0; j < size - i - 1; j++)

2번째 for loop에서 i의 범위가 _i < size - i - 1_인 이유는 한바퀴를 돌때마다 마지막 자리의 숫자가 결정되기 때문에 끝까지 반복할 필요가 없기 때문이다.

output

5 4 3 2 1 

4 5 3 2 1 
4 3 5 2 1 
4 3 2 5 1 
4 3 2 1 5 
4 3 2 1 5 

3 4 2 1 5 
3 2 4 1 5 
3 2 1 4 5 
3 2 1 4 5 

2 3 1 4 5 
2 1 3 4 5 
2 1 3 4 5 

1 2 3 4 5 

---

안전성 확인(unstable)

선택정렬 에서는 멀리 떨어져 있는 원소끼리 swap을 해줬었지만 버블 정렬에서는 바로 옆에 있는것끼리 swap을 한다.
바로 옆에 있는숫자와 꼭 필요한 경우에만 swap을 하기 때문에 value가 바뀌지 않는다.

Element elements[] = { {2,'a'}, {2,'b'}, {1,'c'} };  // key, value

output

2 2 1 
a b c 
1 2 2 
c a b