[알고리즘] Bubble Sort

Abstract

Bubble Sort는 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 이다.

정렬 과정이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 Bubble라는 이름이 붙었다.

Process(Ascending)

1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, ... 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.

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

C++ Code(Ascending)

#include <iostream>
#include <vector>
using namespace std;

void BubbleSort(vector<int> arr){
  int temp = 0;
  for(int i=0; i<arr.size(); i++){     // 1
    for(int j=1; j<arr.size()-i; j++){ // 2
      if(arr[j-1] > arr[j]){ 	       // 3
        swap(arr[j-1], arr[j]);
      }
    }
  }
}

주석 설명

1. 제외될 원소의 개수를 의미한다. 1회전이 끝난 후, 배열의 마지막 위치에는 가장 큰 원소가 위치하기 때문에 하나씩 증가시켜준다.
2. 원소를 비교할 인덱스를 뽑는 반복문이다. j는 현재 원소를 가리키고, j-1은 이전 원소를 가리킨다.
3. 현재 가리키고 있는 두 원소의 대소를 비교한다. 오름차순으로 정렬하기 위해 현재 원소 보다 이전 원소가 더 크다면 자리를 교환한다.

GIF로 이해하는 Bubble Sort

시간복잡도

(n-1) + (n-2) + (n-3) + ... + 2 + 1 ➡ n(n-1)/2 이므로 시간복잡도는 O(n^2).
정렬 여부에 상관없이 비교를 하기 때문에 최선, 평균, 최악의 경우 모두 O(n^2).

공간복잡도

주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(n).

장점

• 구현이 매우 간단하고 소스코드가 직관적이다.
• 정렬하려는 배열 안에서 교환하는 제자리 정렬(in-place sorting) 방식이므로 다른 메모리 공간이 필요하지 않다.
• 동일한 값에 대해 기존의 순서가 유지되는 안정정렬(stable sort) 이다.

단점

• 시간복잡도가 최악, 최선, 평균 모두 O(n^2)로 비효율적이다.
• 정렬되지 않은 원소가 정렬되기 위해 swap이 많이 일어난다.

참고 사이트

Bubble Sort
안정 정렬과 불안정 정렬