자바스크립트의 버블정렬(Bubble Sort)

Haizel·2023년 11월 16일

💡 알바알천 프로젝트

목록 보기

7/11

코딩 테스트의 단골 손님인 정렬 알고리즘은 버블, 선택, 삽입 등 무수히 많은 알고리즘이 존재한다. 아래 Gif를 살펴보면 데이터가 Random인지 혹은 거의 sorte됐는지, 또는 Reversed됐는지에 따라 최적화 정렬 알고리즘이 다르다는 것을 알 수 있다.

출처 : Sorting Algorithms Animations

단편적으로 생각하면 가장 좋은 정렬 알고리즘이 항상 가장 좋은 성능을 보장할 것 같은데 결과로 보았듯이 그렇지만은 않다.
그렇다면 각 알고리즘은 어떻게 구성되어 있길래 이런 차이점이 존재하고, 또 각 정렬 알고리즘은 언제 사용하면 좋을까? 예제와 함께 각 정렬 알고리즘을 낱낱이 파헤쳐보자!

이 글은 JavaScript 알고리즘 & 자료구조 마스터클래스를 참고하여 작성되었습니다.

01. 버블정렬(Bubble Sort)의 개념

버블정렬(Bubble Sort)은 가장 기본적인 정렬 알고리즘으로, 이름 그대로 거품처럼 배열 내 서로 인접한 두 원소들을 비교하고 교환하여 정렬하는 방식을 말한다.

02. 정렬 방법

만약 오름차순으로 정렬한다면, 인접한 두 원소중 더 큰 숫자를 오른쪽으로 교환해가며 정렬한다.

출처 : visualgo

즉 버블 정렬의 작동 방식을 정리해보자면 다음과 같다.

루프를 돌면서 i원소와 i+1원소를 비교한다.

i원소가 더 크다면 i+1원소와 교환한다.

첫번째 루프를 돌면 제일 큰 값이 배열 맨 오른쪽 값으로 위치한다.

다음 루프를 돌 때마다 정렬할 항목이 1개씩 줄어들며 모든 루프가 종료되면 정렬이 완료된다.

03. 버블 정렬 구현

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

console.log(bubbleSort([8, 1, 2, 3, 4, 5, 6, 7])); // [ 1, 2, 3, 4, 5, 6, 7, 8 ]

중첩된 반복문을 통해 인접한 두 원소의 크기를 비교해 위치를 바꿔가며 정렬을 진행한다.
주석 표시된 라인을 보면 arr의 j번째 요소가 다음 요소(j+1)보다 크다면 두 요소를 교환하는 것을 확인할 수 있다.

04. 버블 정렬 최적화

위 구현코드는 문제 없이 구현되지만 한가지 아쉬운 점은 최적화가 이뤄지지 않았다는 점이다. 두 번째 이중문을 살펴보면 j는 arr의 마지막 요소까지 이동하기 때문에 j가 마지막 인덱스일 경우 j+1은 undefined가 되어 불필요한 연산과정을 거치게 된다. 따라서 이 부분을 최적화해보자.

const bubbleSort = (arr) => {
  for (let i = arr.length; i > 0; i--) {
    let isSwap = false;
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // swap
        isSwap = true;
      }
      if (!isSwap) break; // STOP!!
    }
    return arr;
  }
};

console.log(bubbleSort([8, 1, 2, 3, 4, 5, 6, 7])); // [ 1, 2, 3, 4, 5, 6, 7, 8 ]

첫 번째 반복문 상단에 isSwap이라는 변수를 선언하고 교환하지 않았다고 가정해 false값을 할당한다. 그리고 두 번째 이중문에서 교환이 이뤄날 시 변수값을 true로 바꿔준다.
만약 루프를 다 돌기 전에 정렬이 다 이루어졌다면 isSwap값이 true로 바뀌지 않을 것이다. 그 말은 즉은 정렬이 완료되어 더 이상 교환이 이뤄지지 않는다는 의미이다.
따라서 더 이상 교환(swap)이 일어나지 않으면 반복문을 중단한다.

→ 이렇게 간단히 코드 몇 줄을 추가 함으로써 연산과정을 대폭 줄일 수 있다.