[Algorithm] 버블 정렬(Bubble Sort)

버블 정렬이란?

바로 이웃한 두 수를 비교하여, 작은 값을 앞으로 보내는 방법. 가장 효율성은 떨어지는 알고리즘이다.

#include <stdio.h>
#include <iostream>
using namespace std;

int main(void){
    int i,j; // 반복을 위한 변수
    int temp; // 두 수를 교환하기 위한 변수
    int array[10] = {1,6,9,8,2,4,10,3,7,5}; // 정렬할 배열

    for(i=0;i<10;i++){
        for(j=0;j<9-i;j++){
            // 왼 쪽에 있는 수가, 오른쪽에 있는 수보다 크면, 서로 교환 
            if(array[j]>array[j+1]){
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }

    for(i=0;i<10;i++){
        cout<<array[i]<<endl;
    }
     
    return 0;
}

시간 복잡도

1번 반복할 때 마다, 비교하는 요소가 하나 씩 줄어든다. 10개의 요소를 버블 정렬을 통해 정렬 할 때는, 10번 + 9번 + 8번 + ... + 1번 의 연산이 필요하고, 이는 등차수열이므로, [N * (N + 1) / 2]이다.

선택 정렬과 마찬가지로 더하기와 나누기는 N이 엄청 큰 수라고 가정 할 때, 무시할 수 있기 때문에 시간 복잡도는 O(N^2)이다.

그러나, 실제 수행시간은 선택 정렬보다 더 느리다. 선택정렬은 반복 마다 한 번의 swap 과정만 거치지만, 버블 정렬은 한 번 반복마다 계속해서 옆자리 수와 크기를 비교하여 swap 과정을 훨씬 많이 거치기 때문이다.

reference: https://www.youtube.com/watch?v=EZN0Irp2aPs&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=3