[Algorithm] Sorting / Bubble Sort

Bubble Sort(버블 정렬)

버블 정렬 알고리즘이란?

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘으로,
  인접한 두 개의 원소를 비교하여 순서대로 되어 있지 않으면 swap을 합니다.

• 한 사이클을 돌고 나면, 마지막에 가장 큰 수가 위치하게 됩니다. 즉, 매 사이클이 끝날때마다 마지막부터 자리를 잡게됩니다.

• 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고,
  2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외됩니다.
  이렇게 정렬을 한 번 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어나게 됩니다.

버블정렬의 코드는 다음과 같습니다.

#include <iostream>
using namespace std;

int main(){
    int a[10]={2, 5, 8, 7, 6, 10, 1, 3, 9, 4};
    int n = 10;

    for(int i=0; i<n-1; i++){
        for(int j=0; j<n-1-i; j++){
            if(a[j]>a[j+1]) swap(a[j], a[j+1]);
        }
    }

    for(int i=0; i<n; i++) cout<<a[i]<<" ";
    cout<<endl;
}

버블 정렬의 시간 복잡도

• 버블 정렬의 시간복잡도는 최선, 평균, 최악인 경우 모두 O(N^2)입니다.

버블 정렬의 공간 복잡도

• 별도의 메모리 공간이 따로 필요하지 않은 제자리 정렬로,
  공간복잡도는 O(N)입니다.