버블 정렬(Bubble Sort)

하나의 요소를 배열의 길이만큼 돌면서 해당 요소와 다른 요소를 비교 한 후 해당 요소가 더 크다면 위치를 바꾸는 방법입니다.

bubble sort

🫥 어떻게 구현하면 될까요?

  1. 전체 요소를 순회해야 합니다. 👉🏻 for (let i = 0; i < arr.length; i++;) {}

  2. 순회하는 i번쨰 요소는 배열의 마지막 요소까지 비교를 해야하므로 이중 for문을 사용해야겠습니다.

1
2
3
for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length; j++) {}
}
  1. arr[j]가 arr[j + 1]보다 크면 서로의 위치를 바꿉니다.
1
2
3
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;

temp로 이렇게 저렇게 바꾸겠다라는 코드 말고…
하나의 함수를 사용해서 요소를 변경시켜보자구요!

1
2
3
const swap = (arr, idx1, idx2) => {
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};

완성시키면?

1
2
3
4
5
6
7
8
9
10
11
const swap = (arr, idx1, idx2) => {
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};

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

현재 코드의 문제점

현재 코드는 2개의 문제를 가지고 있습니다.

🚧 배열의 범위를 넘어가면서 순회 중!

arr[j]는 arr의 마지막 요소까지 순회합니다. 그렇다면 arr[j + 1]은 뭐가 될까요? 바로 undefined입니다.

우린 45와 undefined를 비교하고 있는 셈이죠. 배열의 범위를 넘기지 않고 탐색할 수 있는 방법이 뭐가 있을까요?

🚧 정렬이 멈추지 않아요!

for문이 종료되기 전에 중간에 정렬이 완료되는 경우가 있을 수 있습니다. 하지만 현재 코드에서는 멈출 수 있는 방법이 없죠. 우리의 코드는 조건에 맞는 for문이 끝날 때까지 멈추지 않고 계속해서 돌아가고 있을 겁니다. 중간에 멈출 수 있으면 좋을 것 같습니다!


해결 방법

첫 번째 문제의 해결 방법은 첫 번째 for문은 거꾸로 돌고 두 번째 for문은 i - 1까지 반복하는 겁니다. 이렇게 되면 배열의 범위 안에서 반복이 가능합니다.

두 번째 문제의 해결 방법은 정렬이 다 되었는지 체크할 수 있는 상태를 가진 변수 noSwap을 하나 설정하는 겁니다.

for문이 시작될 때 true 👉🏻 값을 swap 했다면 false로 변경합니다.
만약 값을 swap하지 않았다면? 👉🏻 noSwap이 true라면 반복문을 빠져나오도록 합니다.


정리해보면

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const swap = (arr, idx1, idx2) => {
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};

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

Review

처음 버블 정렬을 구현해야할 때 순회하는 요소와 그 다음 요소를 비교해서 바꾸면 되겠다라는 막연한 아이디어는 있었는데 디테일하게 구현하려고 하니 너무 막막했읍니다…

제 알고리즘 구현 능력은 여전히 하찮다는 생각을 하며.. 이제 꾸준히 한 문제씩 풀어보려고합니다. 문제 유형별로 카테고리를 나눠서 정리를 해보겠읍니다..!