[알고리즘] 버블 정렬(Bubble Sort)

버블 정렬은 각 단계에서 노드 전체를 검사한다. 차례대로 각 노드에 대해 다음 노드와의 크기를 비교하여 위치를 바꾸고 이런 과정을 원소의 개수만큼 반복한다.

특성

첫 번째 과정에서 가장 큰 원소를 만나면 마지막 노드에 도달할 때까지 계속 교환이 이루어진다.
두 번째 과정에서 두 번째로 큰 원소를 만나면 끝에서 두 번째 노드에 도달할 때까지 계속 교환이 이루어진다.
일반적으로 각 i번째 과정이 끝나면 끝에서 i개의 원소들은 최종 위치에 도달한 것이다.

C++ 구현

template <class RandomIt>
void bubble_sort(RandomIt first, RandomIt last)
{
    while (first != last--)
        for (RandomIt it = first; it < last; ++it)
            if (*it > *(it+1))
            {
                auto temp = *it;
                *it = *(it+1);
                *(it+1) = temp;
            }
}

template <class RandomIt, class Compare>
void bubble_sort(RandomIt first, RandomIt last, Compare comp)
{
    while (first != last--)
        for (RandomIt it = first; it < last; ++it)
            if (comp(*it, *(it+1)))
            {
                auto temp = *it;
                *it = *(it+1);
                *(it+1) = temp;
            }
}

[first, last) 범위의 원소를 오름차순으로 버블 정렬하는 코드이다. 두 번째 버전을 이용하면 두 원소를 매개변수로 하는 bool형 함수를 대입하여 다른 순서로 정렬할 수 있다.