버블 정렬 (Bubble Sort)

한쪽에서 시작해서 바로 옆값과 서로 비교해서 값을 한쪽으로 밀어내는 방식

https://simple.wikipedia.org/wiki/Bubble_sort

Bubble sort - Simple English Wikipedia, the free encyclopedia

// Bubble Sort
{
    bool isSwapped = false;
    for (int i = 0; i < n - 1; i++)
    {
        isSwapped = false;
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
                isSwapped = true;
            }
        }
        if (!isSwapped)
        {
            break;
        }
    }
}

Worst Case: O(n^2) 여서 빠른 정렬이라고 할 수는 없으나,

이미 거의 정렬이 되어있는 상태에서 정렬을 하는 경우라면 버블소트는 정렬하는 중간에 정렬이 완성되었는지 미리 확인이 가능하다는 장점이 있기때문에 조기 종료를 할 수 있다는 장점이 있다.

또한 Stable 한 정렬 알고리즘이다.

 

stable?

-> 기존의 배열 상태에서 정렬을 완료했을때 값이 같은 값의 원소의 순서를 기존 배열 그대로 바꾸지 않는다는 뜻. key 값과 value 값이 있는데 value로 sorting을 했을때 key값의 순서는 기존의 순서를 유지한다는 뜻.