[정렬] Bubble Sort

버블 정렬의 개념

버블 정렬 수행도

버블 정렬이란?

서로 인접한 두 원소의 대소를 비교하고, 두 원소의 위치가 바뀌어야 한다면 자리를 교환하며 정렬하는 알고리즘이다.
선택 정렬과 기본 개념이 유사하지만, 버블정렬은 선택정렬과 다르게 SWAP이 계속적으로 일어난다.

버블 정렬의 동작 방식과 구현

동작 방식

1. n-1개의 데이터의 위치만 찾으면 되므로 n-1번 반복한다. (n-1개의 데이터의 위치가 정해지면 나머지 1개는 자동 정렬)

  1-1. 앞에서부터 버블처럼 올라가며 2개의 데이터씩 짝지어 비교한다. 

        1-1-1. 2개의 데이터를 비교하여 위치가 바뀌어야 한다면 SWAP한다. 

1번을 한번 반복할 때마다 정렬되지 않은 데이터들 중 가장 큰 값이 뒤로 이동한다. (즉, 반복 한번 당 하나의 데이터가 무조건 정렬됨)

구현

  for(var i=array.length-1; i>=0; i--) {
    for(var j=0; j<i; j++) {
        if(array[j] > array[j+1]) {
          SWAP(j, j+1);
        }
    }
  }
  
  function SWAP(x, y) {
    var temp = array[x]
    array[x] = array[y];
    array[y] = temp; 
  }

심심해서 자바스크립트로 구현!

Big-O

비교 횟수

1. 최상, 최악, 평균 모두 일정함 (정렬이 되어있든 아니든 항상 2개의 원소를 비교하기 때문에) 
2. n-1, n-2, ...., 2, 1 번 이루어지기 때문에 총 n(n-1)/2번 일어남 

교환 횟수 

1. 만약 입력 데이터가 역순으로 나열되어 있는 경우, SWAP 연산은 비교 횟수만큼 일어남 
2. SWAP 연산은 3번의 이동이 필요하므로 총 연산 수는 3 * n(n-1)/2 
3. 따라서 T(n) = O(n^2)

버블 정렬의 장단점

장점 

1. 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 구현이 매우 간단하다. 
2. 배열 안에서 교환하기 때문에 추가 메모리가 필요하지 않다.
3. Stable Sort이다.

단점

1. 인접한 요소와 비교 후 바로 SWAP이 일어나기 때문에 많은 SWAP 연산이 수행된다.