[Algorithm] Bubble Sort(버블 정렬)

Code

Python

def bubble_sort(a):
    for i in range(len(a)-1,0,-1):
        flag = False
        for j in range(i):
            if(a[j]>a[j+1]):
                a[j], a[j+1] = a[j+1], a[j]
                flag = True
        if not flag: break
a = [10, 4, 5, 1, 8, 6, 2, 7, 9, 3]

print(a)
bubble_sort(a)
print(a)

 

C++

#include <iostream>

using namespace std;

const int ARRAY_SIZE = 10;

void bubble_sort(int a[]){
  for(int i=ARRAY_SIZE-1; i>0; i--){
    bool flag=false;
    for(int j=0; j<i; j++){
      if(a[j]>a[j+1]) swap(a[j], a[j+1]);
      flag=true;
    }
    if(!flag) break;
  }
}

int main(){
  int a[ARRAY_SIZE] = {10, 4, 5, 1, 8, 6, 2, 7, 9, 3};

  for(int i=0; i<ARRAY_SIZE; i++){
    cout << a[i] << ' ';
  }
  cout << '\n';
  bubble_sort(a);
  for(int i=0; i<ARRAY_SIZE; i++){
    cout << a[i] << ' ';
  }
  return 0;
}

정리

처음부터 끝까지 순서대로 인접한 두 원소를 비교하여 교환해 정렬하는 알고리즘

 

시간복잡도

n-1, n-2, ... 2, 1 비교연산

→ n*(n-2)/2 비교연산

→ O(n^2)

 

특징

stable sort

in-place sort