졍's 기술 블로그

버블 정렬(Bubble Sort)

: 옆에 있는 값과 비교해 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법

버블 정렬 Sequence

더보기

한 번 반복이 끝났을 때 가장 큰 값이 가장 마지막 위치로 이동

코드

#include <iostream>
using namespace std;

int main(void){
    int i, j, tmp;
    int arr[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    for(i=0;i<10;i++){
        for(j=0;j<9-i;j++){ // i for문이 1번 반복될 때마다 가장 마지막 위치의 원소는 채워지기 때문에 idx 9-i까지만 확인
            if(arr[j] > arr[j+1]){
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }

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

출력

1 2 3 4 5 6 7 8 9 10

시간 복잡도

10 + 9 + 8 + ... + 1

= 10 * (10 - 1) / 2

= N * (N - 1) / 2

= O(N^2)

실제로 실행시켜보면 Bubble Sort가 Selection Sort보다 더 느리게 작동한다.
: Bubble Sort는 당장 옆에 있는 것과 비교해 자리를 바꾸는 연산을 수행하며, 자리를 바꾸는 연산은 총 3번의 연산을 필요로 하기 때문에 컴퓨터가 실질적으로 수행해야하는 명령어가 더 많기 때문이다.
반면에 선택 정렬은 가장 작은 수를 찾아 마지막에 한 번만 자리를 바꾸는 연산을 수행한다.

참고로, 정렬 알고리즘 중 가장 느린 건 Bubble Sort이다.