[C++/정렬] 버블 정렬

정렬은 숫자를 오름차순 또는 내림차순으로 정리한 것이다.

​

이러한 정렬 중

버블 정렬이란?

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.

-> 인접한 2개의 원소를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하게 된다.

​

(==선택정렬, 두개의 기본 개념이 비슷하다)

​

버블 정렬 알고리즘 구체적 개념

버블 정렬은 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, 이런 식으로 (마지막 - 1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하게 된다.

​

1회전을 수행하고 나면 가장 큰 원소는 맨 뒤로 이동하게 된다. 그러므로 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어나게 된다.

​

< 버블 정렬 예시 >

#include <iostream>
using namespace std;

int main() {
    int array[10]={4, 6, 7, 2, 1, 5, 9, 10, 3, 8};
    int temp;
    
    for(int i=0; i<10; i++){
        for(int j=0; j<10-1-i; j++){
            if(array[j]>array[j+1]){
                temp=array[j];
                array[j]=array[j+1];
                array[j+1]=temp;
            }
        }
    }
    for(int i=0; i<10; i++){
        cout<<array[i]<<endl;
    }
    return 0;
}

버블 정렬의 장단점

- 장점: 구현하기 매우 쉬움

​

- 단점: 시간 복잡도가 매우 높음. 시간이 오래 걸려서 거의 사용하지 않음.