자바스크립트로 구현한 버블정렬 알고리즘 (Bubble sort in Javascript)

남양주개발자

2020. 11. 16. 08:56

728x90

자바스크립트로 구현한 버블정렬 (Bubble sort in Javascript)

'버블정렬' 알고리즘은 코딩 테스트를 준비할 때 가장 처음 접하는 정렬 알고리즘 중 하나입니다. 코딩 테스트에도 한번씩 등장하는 '버블정렬' 알고리즘에 대해서 오늘 확실하게 개념을 잡고 이해해보도록 하겠습니다. 구현 예시의 언어는 자바스크립트로 구현되었으나 알고리즘의 기본 컨셉은 동일하기 때문에 자바스크립트 이외에 다른 언어로 구현하셔도 무방합니다.

버블 정렬이란?

거품 정렬이라고도 불리는 버블 정렬은 두 인접한 원소를 검사하여 정렬(오름차순, 내림차순)하는 방법입니다. (오름차순이라면 작은 값부터 큰 값 순으로 정렬이 될 것이고, 내림차순이라면 큰 값부터 작은 값 순으로 정렬이 되겠죠?)

버블정렬 알고리즘 예시

버블정렬 알고리즘을 좀 더 쉽게 이해하기 위해 코드를 보기 전에 해당 자료를 한번 보시면 좀 더 이해가 쉬울 수 있습니다.

정렬 과정

버블정렬은 인접한 두 요소를 마지막 요소까지 모두 비교하며 교환하거나 유지하면서 정렬합니다.
1회전을 수행한 후 정렬 조건에 따라 가장 크거나 작은 요소가 맨 뒤로 이동하기 때문에 2회전부터는 가장 끝에 있는 요소는 정렬에서 제외됩니다. 쉽게 말해 정렬 1회전을 수행할 때마다 정렬에서 제외되는 요소가 1개씩 늘어나게 됩니다.

배열의 초기 값이 [9,2,5,1,3]로 저장되어 있다고 가정하고 배열의 순서를 오름차순으로 정렬해보도록 하겠습니다.

// 정렬 전 : [9,2,5,1,3]

// 1회전
[9,2,5,1,3] -> [2,9,5,1,3] -> [2,5,9,1,3] -> [2,5,1,9,3] -> [2,5,1,3,9]

// 2회전
[2,5,1,3,9] -> [2,5,1,3,9] -> [2,1,5,3,9] -> [2,1,3,5,9]

// 3회전
[2,1,3,5,9] -> [1,2,3,5,9] -> [1,2,3,5,9]

// 4회전
[1,2,3,5,9] -> [1,2,3,5,9]

// 최종 정렬 결과 : [1,2,3,5,9]

1회전

1회전에서 인덱스 0번째인 9부터 비교를 시작합니다. 9와 2를 비교한 결과 9는 2보다 크기 때문에 9와 2를 swap합니다. 그다음 요소인 5와 현재 요소인 9를 비교합니다. 9는 5보다 크기 때문에 swap합니다. 그다음 요소인 1과 현재 요소인 9를 비교합니다. 9는 1보다 크기 때문에 swap합니다. 마지막 요소인 3과 현재 요소 9를 비교합니다. 9는 3보다 크기 때문에 swap합니다.

2회전

2회전에서 인덱스 0번째인 2부터 비교를 시작합니다. 다음 요소 5와 비교한 결과 2는 5보다 작기 때문에 유지합니다. 다음 요소인 1과 현재 요소 5를 비교합니다. 5는 1보다 크기 때문에 swap합니다. 다음 요소 3과 현재 요소 5와 비교합니다. 5는 3보다 크기 때문에 swap합니다. 다음 요소인 9는 이미 정렬이 완료되었기 때문에 순회를 종료합니다.

3회전

3회전에서 인덱스 0번째인 2부터 비교를 시작합니다. 다음 요소 1과 비교한 결과 2는 1보다 크기 때문에 swap합니다. 다음 요소인 3과 현재 요소 2를 비교합니다. 현재 요소 2는 3보다 작기 때문에 유지합니다. 다음 요소 5는 이미 정렬이 완료되었기 때문에 순회를 종료합니다.

4회전

4회전에서 인덱스 0번째인 1부터 비교를 시작합니다. 다음 요소 2와 비교한 결과 1은 2보다 작기 때문에 유지합니다. 다음 요소인 3은 이미 정렬이 완료되었기 때문에 순회를 종료합니다.

비교 횟수

위 버블정렬의 예시를 보면 알 수 있듯이 버블 정렬을 통해 5개의 요소로 구성된 배열을 정렬하게 되면 총 비교 횟수는 4회 + 3회 + 2회 + 1회 = 총 10회입니다. 즉 항목의 개수가 N이면 (N - 1) + (N - 2) + (N - 3) + ... + 1이 총 비교 횟수가 되는 것입니다. 좀 더 패턴으로 수학 공식화한다면 N*(N-1)/2가 되는 것입니다.

버블정렬의 특징(장단점)

시간복잡도

버블 정렬의 시간 복잡도는 최상, 최악, 평균 모두 O(n^2)의시간복잡도(n*(n-1)/2)를 가지고 있습니다. 그 이유는 버블정렬은 이미 정렬이 되어 있든 안되어 있든 상관없이 n개의 요소가 있을 때 n개에 대해서 각 n번의 순회를 돌기 때문에 모두 동일한 시간복잡도를 가지고 있는 것입니다.

장점

단순하게 인접한 두 요소를 비교하기 때문에 구현이 굉장히 단순하다.

단점

수행 시간이 굉장히 오래 걸린다.
불필요한 교환이 이뤄질 가능성이 크다. (최종 단계에서는 현재 위치가 맞음에도 불구하고, 인접한 두 요소 간의 비교에 의해 위치가 변경된다.)

소스 코드

아래 소스 코드는 자바스크립트(Javascript) ES6 문법으로 구현한 예시입니다. 자바스크립트(Javascript) ES6 문법 중 구조 분해 할당 구문을 활용해서 요소 swap을 처리했습니다.

// 버블소트 ES6
const bubblesort = (arr) => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - (i + 1); j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] // swap
      }
    }
  }

  return arr;
}

swap 헬퍼 함수를 만들어서 처리할 수도 있습니다.

const swap = (arr, i) => {
  const temp = arr[i];
  arr[i] = arr[i + 1];
  arr[i + 1] = temp;
}

const bubblesort = (arr) => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - (i + 1); j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j) // swap
      }
    }
  }

  return arr;
}

정리

생각보다 버블 정렬의 구현 난이도는 쉬운 편이었습니다. 인접한 두 요소의 값만 비교해서 원하는 정렬 조건(오름차순, 내림차순)에 따라서 인접한 두 요소를 변경(swap)할지 말지에 대해서만 결정하면 됩니다. 하지만 앞으로 다른 정렬 알고리즘을 다루면서 다시 한번 언급하겠지만, 버블정렬의 퍼포먼스는 앞에서 봤듯이 좋은 편은 아니기 때문에 실제 업무나 구현을 위해 사용할 때는 잘 사용되지는 않습니다. 기본적인 정렬 알고리즘의 동작 방식을 이해하기 위해 다루는 정렬 알고리즘이라고 생각하시면 됩니다.

728x90

그리드형