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


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

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


버블 정렬(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 로 정렬됨을 확인할 수 있습니다.



소스 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
 
using namespace std;
 
void swap(int *a, int * b){
    int temp;
    temp = *a;
    *= *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;
}
 
cs



코드 설명


배열 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차식이 됩니다.


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











+ Recent posts