3. 거품 정렬(Bubble Sort)

거품 정렬의 개념

거품 정렬은 단순히 처음부터 끝까지 두 개의 값을 서로 비교해가면서 정렬한다.

 

▼ 비교하는 모습이 거품과 같다.

두 값을 비교해서 교환하는 것이 마치 거품이 일어나는 모습과 비슷하다고 해서 거품 정렬이라 부른다.

 

▼ 거품 정렬 알고리즘 도식화

거품 정렬은 한번 외부 순환문을 돌 때마다 목표 방향 끝자리는 최댓값 혹은 최솟값이 정렬된다.

그렇기 때문에 내부 순환 문의 목푯값이 하나씩 줄어드는 것이 알고리즘의 핵심이다.

거품 정렬의 성능[O(n²)]

정렬할 자료의 수의 제곱에 비례하여 늘어난다.

순차 정렬과 마찬가지로 단순 무식한 방법인 만큼 거품 정렬은 거의 모든 경우에서 최악의 성능을 보여준다.

그리고 정렬이 이미 완료된 경우엔 최선의 성능을 보이는 것도 순차 정렬과 같다.

 

순차 정렬과 마찬가지로 실무에서는 잘 쓰이지 않는다고 한다.

C99

▼ 관련 개념

Loop & Pointer & Call By Address

 

▼ 구현 코드

int Compare(int lhs, int rhs)
{
    return (lhs - rhs);
}

void Swap(int* lhs, int* rhs)
{
    int _temp = *lhs;
    *lhs = *rhs;
    *rhs = _temp;
}

// 왼쪽->오른쪽 정렬
void BubbleSort(int iArr[], int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = 0; j < length - i -1; j++)
        {
            if ( Compare(iArr[j], iArr[j + 1]) > 0 )
                Swap(&iArr[j], &iArr[j + 1]);
        }
    }
}

// 왼쪽<-오른쪽 정렬
void BubbleSort(int iArr[], int length)
{
    for (int i = length; i > 1; i--)
    {
        for (int j = 1; j < i; j++)
        {
            if ( Compare(iArr[j - 1], iArr[j]) > 0 )
                Swap(&iArr[j - 1], &iArr[j]);
        }
    }
}

어디부터 정렬하는지의 차이일 뿐 내부 개념은 동일하다.

CPP B.11

▼ 관련 개념

Loop & STD

 

▼ 구현 코드

#include <algorithm>

int Compare(int lhs, int rhs)
{
    return (lhs - rhs);
}

// 왼쪽->오른쪽 정렬
void BubbleSort(int iArr[], int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = 0; j < length - i - 1; j++)
        {
            if ( Compare(iArr[j], iArr[j + 1]) > 0 )
                std::swap(iArr[j], iArr[j + 1]);
        }
    }
}

// 왼쪽<-오른쪽 정렬
void BubbleSort(int iArr[], int length)
{
    for (int i = length; i > 1; i--)
    {
        for (int j = 1; j < i; j++)
        {
            if ( Compare(iArr[j - 1], iArr[j]) > 0 )
                std::swap(iArr[j - 1], iArr[j]);
        }
    }
}

CPP A.98 <algorithm> 라이브러리를 사용한 방법이다.

CPP A.11

▼ 관련 개념

Loop & Template & STD

 

▼ 구현 코드

#include <utility>

template<typename T>
int Compare(T lhs, T rhs)
{
    return (lhs - rhs);
}

// // 왼쪽->오른쪽 정렬
template<typename T, typename L>
void BubbleSort(T tArr[], L length)
{
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = 0; j < length - i - 1; j++)
        {
            if ( Compare(tArr[j], tArr[j + 1]) )
                std::swap(tArr[j], tArr[j + 1]);
        }
    }
}

// // 왼쪽<-오른쪽 정렬
template<typename T, typename L>
void BubbleSort(T tArr[], L length)
{
    for (int i = length; i > 1; i--)
    {
        for (int j = 1; j < i; j++)
        {
            if ( Compare(tArr[j - 1], tArr[j]) > 0)
                std::swap(tArr[j - 1], tArr[j]);
        }
    }
}

주조(Template)를 사용하여 어떤 변수형이 오더라도 비교하고 정렬할 수 있는 코드가 되었다.

배열의 길이가 int형이 아닌 long이나 long long으로 오더라도 문제없이 작동한다.

 

CPP A.11에서는 std::swap 함수가 <utility>로 이동했다.