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

저번 글에서 언급했듯이 이제부터 본격적으로 정렬 알고리즘에 대해서 알아보도록 하겠습니다.

이번 시간에는 기본적인 정렬 알고리즘 세 개 중 하나인 버블 정렬입니다.

(삽입과 선택은 다음 시간에 다루겠습니다!)

버블 정렬(Bubble Sort) - 안정 정렬

버블 정렬이란 인접한 두 원소를 계속 비교해 나가며 최종 정렬 값을 하나씩 완성해 나가는 방법입니다.

글로써는 이해하기가 어려울 수 있으니 그림으로 자세하게 설명드리도록 하겠습니다.

위 그림은 주어진 데이터를 오름 차순으로 버블 정렬하는 과정입니다.(데이터의 사이즈 n = 5)

정렬 과정은 데이터의 수 - 1 만큼 회전(반복)하며 큰 값을 결정해 나가는 것입니다.

다시 말해 1회전 - 첫 번째로 큰 값(7), 2회전 - 두 번째로 큰 값(5) ... 마지막으로  n-1 번째로 큰 값(2)을 결정하고 끝입니다.

(n번째 큰 값 1은 n-1번째로 큰 값이 정해지면 알아서 정해지므로 n-1번째 까지만 진행합니다.)

최종적으로 7 - 3 - 2 - 1 -5 의 데이터가 1 -2 - 3 - 5 - 7 로 정렬됨을 확인할 수 있습니다.

소스 코드

#include <iostream>
 
using namespace std;
 
void swap(int *a, int * b){
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
 
int main()
{
    int a[5] = {7,3,2,1,5};
    bool endFlag;
    
    //정렬
    for(int i = 0 ; i < 4;i++){
        endFlag = true;
        for(int j=0; j <4-i;j++){
            if(a[j]>a[j+1]){
                swap(&a[j],&a[j+1]);
                endFlag = false;
            }
        }
        if(endFlag) break;
    }
    
    //출력
    for(int i = 0; i <=4; i++)
        cout << a[i] <<" ";
    return 0;
}
 

코드 설명

배열 a : 정렬하고자 하는 데이터 입니다.

endFlag : 정렬 과정 중에서 데이터의 교환(swap)이 일어나지 않으면, 정렬된 상태이므로 이 때 탈출하기 위한 신호(Flag) 변수입니다.

Line 5 - 10 : 데이터의 위치를 바꾸는 함수 정의입니다.

Line 19 : 매 회전마다 교환 여부를 파악하기 위해 true로 초기화

Line 21 -24 : 인접한 데이터의 순서가 맞지 않으면 교환하고 endFlag를 false로 변경하여 탈출하지 않습니다.

Line 26 : endFlag 값을 보고 정렬 완성 상태를 파악한 후 반복문을 끝낼지 결정하는 부분입니다.

시간 복잡도

버블 정렬을 사용했을 때 최악의 경우는 정렬하고자 하는 방향의 반대로 구성된 데이터들을 정렬할 때 입니다.

다시 말해서 오름차순으로 정렬하고자 할 경우 내림차순으로 정렬된 데이터들을 오름차순으로 정렬하는 경우입니다.

이 경우에는 endFlag 인해서 중간에 break가 되지 않고, 끝까지 돌아갑니다.

입력 데이터의 크기가 n 일때 시간복잡도를 계산해보면,

1회전 : n-1번비교, 2회전 : n-2번 비교  n-1회전 : 1번 비교

이를 계산하면 n-1 부터 1까지 등차 수열의 합이므로 최고 차항은 n에 대한 2차식이 됩니다.

따라서 시간복잡도는 이 됩니다.