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

버블 정렬이란?

두 인접한 원소를 검사하여 정렬하는 알고리즘이다.

버블 정렬은 기본적으로 배열의 두 수(a,b)를 선택한 뒤, 만약 그 두 수가 정렬되었다면 놔두고 아니라면 두 수를 바꾸는 방식으로 진행된다. 오름차순으로 정렬할 때는 a<b여야 정렬된 것으로 판단한다. 이를 배열의 처음부터 끝까지 반복한다.

---

버블 정렬의 작동 과정

인접한 원소들을 비교하여 크기 순서가 잘못되어 있으면 교환(swap)한다. 이 과정을 리스트가 정렬될 때까지 반복한다.

1. 가장 큰 수인 6을 정확한 위치에 놓는다.

검사횟수 n = 배열갯수 - 1

2. 가장 큰 수인 6을 맨 끝으로 고정하고 남은 노드들을 검사하여 두번째로 큰 5를 정확한 위치에 놓는다.

검사횟수 n = 배열갯수 - 2

3. 조건에 맞게 정렬된 5, 6을 고정하고 남은 노드들을 검사하여 3번째로 큰 수를 정확한 위치에 놓는다.

검사횟수 n = 배열갯수 - 3

---

배열의 시간 복잡도

버블정렬의 작동과정을 보면 (N-1)+(N-2)+(N-3)...의 형태로 검사 횟수가 점점 일정하게 줄어드는 것을 확인할 수 있다.

즉 등차수열( 차이가 일정한 수열 )로 표현되므로, 등차수열 공식이 적용된다

이 값은 O(N^2)에 비례하기 때문에, 버블정렬의 시간 복잡도는 다음과 같다.

최상	O(N) - 처음부터 옳은 순서로 리스트가 정렬되어 있을 때
평균	O(N^2)
최악	O(N^2)

 

버블 정렬 코드 예시 (JS)

 

function bubble(arr) {
  let result = arr;
  console.log(result);

  for (let i = 0; i < result.length - 1; i++) {
  // 배열의 길이만큼 검사 반복
    for (let j = 0; j < result.length - i - 1; j++) {
      // 검사를 마칠 때마다 올바르게 놓인 값들을 제외(-i)하고 검사
      // j는 마지막에 비교할 원소를 넘지 않게 함

      if (result[j] > result[j + 1]) {
      //배열의 다음 값이 이전값보다 클 때 조건 실행
        let i = 0; //swap용 변수
        
        i = result[j];
        result[j] = result[j + 1];
        result[j + 1] = i;
        //조건에 해당하는 값 swap
      }

    }
  }
  return result;
}

 

 

bubble함수에 [5,4,2,3]인 배열(arr)을 주어 호출하고

i와 swap전, 후 result[j]값을 console에서 출력하여 결과를 확인했다.

 

 

참조 : https://www.geeksforgeeks.org/bubble-sort-algorithm/