3. 버블 정렬(Bubble Sort)

#버블 정렬 알고리즘

1. 매 단계마다 처음부터 마지막까지 차례대로 인접한 두 원소를 비교하여 뒤에 있는 원소가 앞의 원소보다 작은 경우 두 원소를 교환

2. 각 단계 수행 후 최대값이 마지막으로 이동하므로, 마지막 원소는 정렬대상에서 제외

3. 만약 끝까지 가면서 교환이 일어나지 않았으면 정렬이 되어 있는 것

 

 

#구현

#include <iostream>
using namespace std;

void bubblesort(int* a, int n);
void swap(int* a, int* b);

int main(){
    int n;
    cin>>n;
    int* a= new int[n];
    for(int i=0; i<n; i++)
        cin>>a[i];

    bubblesort(a,n);

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

    return 0;
}

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

void swap(int* a, int* b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

//개선된 버블정렬: 정렬이 이미 되어있다면 더이상 비교x
seletionsort(int* a, int n){
    for(int i=n-1; i>0; i--){
        int sorted=1;
        for(int j=0; j<i; j++){
            if(a[j]>a[j+1]){
                swap(&a[j], &a[j+1]);
                sorted=0;
            }
        }
        if(sorted) break;
    }
}

 

#시간복잡도 분석

원소 비교횟수 = n-1 + n-2 + n-3 + ... + 3 + 2 + 1 = n(n-1)/2

=> O(n*n)