[알고리즘] 버블 정렬 알고리즘

 

안녕하세요

정렬 알고리즘 중 가장 구현하기 쉬운 버블 정렬 알고리즘에 대해 알아보도록 하겠습니다.

 

버블 정렬 알고리즘

배열등 리스트에서 인접한 데이터들을 비교하여 정렬하는 알고리즘

 

구현 방법

오름차순 기준(제일 작은 값이 앞으로, 제일 큰 값이 뒤로 정렬)으로 설명하면,
첫 번째 데이터를 모든 데이터와 비교하면서 첫 번째 데이터가 더 크면 서로 스왑 하고,
다음 두 번째 데이터를 모든 데이터와 비교하면서 두 번째 데이터가 더 크면 서로 스왑 하는 과정을
마지막 데이터-1까지 계속 반복합니다.

 

예제

배열 arrData에 100, 20, 10, 12, 5 값이 있다면, 이 배열 데이터를 정렬하면 다음과 같이할 수 있습니다.

arrData의 첫번째 값 100을 두 번째 값 20과 비교했을 때, 100이 더 크기 때문에 두 값을 스왑 합니다.(20, 100, 10, 12, 5)
arrData의 두번째 값 100을 세 번째 값 10과 비교했을 때, 100이 더 크기 때문에 두 값을 스왑 합니다.(20, 10, 100, 12, 5)
arrData의 세번째 값 100을 네 번째 값 12과 비교했을 때, 100이 더 크기 때문에 두 값을 스왑 합니다.(20, 10, 12, 100, 5)
arrData의 네번째 값 100을 다섯 번째 값 5과 비교했을 때, 100이 더 크기 때문에 두 값을 스왑 합니다.(20, 10, 12,  5, 100)

 

arrData의 첫번째 값 20을 두 번째 값 10과 비교했을 때, 20이 더 크기 때문에 두 값을 스왑 합니다.(10, 20, 12,  5, 100)
arrData의 두번째 값 20을 세 번째 값 12과 비교했을 때, 20이 더 크기 때문에 두 값을 스왑 합니다.(10, 12, 20, 5, 100)
arrData의 세번째 값 20을 네 번째 값 5과 비교했을 때, 20이 더 크기 때문에 두 값을 스왑 합니다.(10, 12, 5, 20, 100)

 

arrData의 첫번째 값 10을 두 번째 값 12과 비교했을 때, 10이 더 작기 때문에 두 값을 스왑 하지 않습니다.(10, 12, 5, 20, 100)
arrData의 두번째 값 12를 세 번째 값 5과 비교했을 때, 12이 더 크기 때문에 두 값을 스왑 합니다.(10, 5, 12, 20, 100)

 

arrData의 첫번째 값 10을 두 번째 값 5과 비교했을 때, 10이 더 크기 때문에 두 값을 스왑 합니다.(5, 10, 12, 20, 100)

 

C++로 구현

#include <iostream>
using namespace std;
 
void main()
{
    int arrData[5] = { 100, 20, 10, 12, 5 };
    int nTemp;
    int nSize = sizeof(arrData) / sizeof(int);
 
    cout << "before : ";
    for( int i = 0; i < 5; i++ )
        cout << arrData[i] << " ";
    cout << endl;
 
    for( int i = 0; i < nSize-1; i++ )
    {
        for( int j = 0; j < nSize-i-1; j++ )
        {
            if( arrData[j] > arrData[j+1] )
            {
                nTemp = arrData[j];
                arrData[j] = arrData[j+1];
                arrData[j+1] = nTemp;
            }
        }
    }
    cout << "after : ";
    for( int i = 0; i < 5; i++ )
        cout << arrData[i] << " ";
    cout << endl;
}