버블 정렬 알고리즘(Bubble Sort)

인프런 - 파이썬으로 배우는 알고리즘 기초 강의 이미지

✔ 버블 정렬(Bubble Sort)

버블 정렬은 구현이 간단하지만 가장 비효율적인 알고리즘입니다.

버블 정렬은 바로 옆에 있는 두 원소를 비교하면서 정렬하는 알고리즘입니다.

 

오름차순일 경우, 두 원소를 비교해서 작은 값을 앞으로 보내고 큰 값을 뒤로 보내 가장 큰 값이 맨 뒤로 가면서 뒤에서부터 정렬이 완료되는 방법입니다.

내림차순일 경우, 두 원소를 비교해서 큰 값을 앞으로 보내고 작은 값을 뒤로 보내 정렬이 됩니다.

 

✔ 버블 정렬 동작 과정

왼쪽 → 오른쪽 순으로 봐주시기 바랍니다.

 

 

1. 리스트의 첫 번째 인덱스를 교환(Swap) 대상으로 선정하고, 가장 가까운 두 번째 인덱스를 비교해서
   교환 대상의 값이 더 크면 위치를 교환하고, 더 크지 않으면 넘어갑니다
2. 리스트의 두 번째 인덱스를 교환(Swap) 대상으로 선정하고, 가장 가까운 세 번째 인덱스를 비교해서
   교환 대상의 값이 더 크면 위치를 교환하고, 더 크지 않으면 넘어갑니다
3. 계속 인덱스를 증가시키면서 끝까지 비교합니다
4. 끝까지 비교하면 맨 뒤부터 정렬이 완료됩니다(한 번의 반복문이 완료된 상태. 1회전 결과)
5. 뒤에서부터 앞에까지 정렬이 모두 완료될 때까지 반복합니다

 

✔ 버블 정렬 구현(C++)

#include <iostream>
using namespace std;

const int LEN = 7;
int arr[LEN] = {2, 9, 5, 6, 4, 1, 7};

void BubbleSort(int *arr, int len) {
  int temp;
  
  for(int i=0; i<len; ++i) {
    /*
      반복문 len-1-i 까지 하는 이유
      -i하는 이유는 버블 정렬은 뒤에서부터 정렬이 완료됨
      -1하는 이유는 비교 대상과 옆에꺼를 비교하기 때문에
      마지막까지 반복하면 안된다(마지막+1로 인해 OutofBound)
    */
    for(int j=0; j<len-1-i; ++j) {
      if(arr[j] > arr[j+1]) {
        // Swap 부분
        temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  
    BubbleSort(arr, LEN);

    for(int i : arr)
      cout << i << " ";
    return 0;
}

 

✔ 버블 정렬 시간 복잡도

버블 정렬의 시간 복잡도는 아래와 같다.

$$ O(N^2) $$

 

(N-1) + (N-2) + ... + 2 + 1 = N(N-1)/2 = N * N = O(N^2)

 

선택 정렬과 똑같은 시간 복잡도이지만 정렬 중 가장 비효율적인 이유는 버블 정렬은 가장 가까운 두 숫자를 비교해서 Swap을 매번 연산하기 때문에 더 느린 비효율적인 알고리즘입니다.

 

즉, 선택 정렬의 경우 전체 리스트를 돌면서 하나의 최솟값을 구하고 마지막에 Swap을 1번 진행하지만 버블 정렬의 경우는(오름 차순 기준) 전체 리스트에서 가장 가까운 두 숫자를 비교해서 작은 값을 앞으로 Swap 해주는 연산을 매번 진행하기 때문입니다.

위의 그림으로만 봐도 왜 비효율적인지 알 수 있을 것 같습니다.

시간 복잡도에 대한 좀 더 자세한 내용은 아래의 내용에서 확인하세요.
시간 복잡도

 

 

 

 

🔗 Reference

• 버블 정렬