버블 정렬(Bubble Sort)

버블 정렬이란?

배열을 숫자 오름차순으로 정렬한다면 더 큰 숫자가 한 번에 하나씩 뒤로 이동하여 정렬하는 개념이다.

즉, 배열의 모든 요소를 처음부터 차례대로 순회하면서 기준 요소와 기준 요소의 그 다음 요소와 크기를 비교하고 기준 요소가 더 크다면 서로 교환하여 정렬하는 방식이다.

참고: https://visualgo.net/en/sorting

위 영상을 토대로 추가로 설명하자면
오름차순으로 정렬될 때까지 매 순회(인덱스가 0에서 배열 끝에 닿을 때)마다 그다음 요소와 비교하여 그 다음 요소보다 크다면 서로 교환하는 원리라고 할 수 있다.

이렇게 되면 매 순회마다 가장 큰 수가 맨 우측에 정렬되는데 이로써 순회 마다 비교 횟수를 줄여나갈 수 있다. 비교횟수를 줄여나가려면 변수 두개를 사용하여 이를 제어해야하기 때문에 이중for문으로 작성할 필요가 있겠다.

버블 정렬 구현

function bubbleSort(arr) {
  // i와 j를 활용하여 매 반복마다 비교 횟수를 줄여나갈 수 있다.
  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }

  return arr;
}

bubbleSort([37, 45, 29, 8]); // [8, 29, 37, 45]

버블 정렬 최적화

만약 정렬을 하다가 중간에 오름차순 정렬이 완료되었다고 해도 최적화를 하지 않으면 정렬이 완료된 상태에서도 계속 비교해 나갈 것이다. 그래서 변수를 추가하여 요소간 위치 교환이 일어나지 않았다면 for문을 빠져나오도록 구현하는데 좋다.

function bubbleSort(arr) {
  // 한바퀴 순회를 했을 때 요소간 위치교환이 발생했는지
  let isSwapped;
  
  for (let i = arr.length; i > 0; i--) {
	isSwapped = false;
    
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        
        // 만약 교환이 일어난다면 false로 변경하여
        // for문을 빠져나가지 않는다.
        isSwapped = true;
      }
    }
    
    if (!isSwapped) break;
  }

  return arr;
}

bubbleSort([37, 45, 29, 8]); // [8, 29, 37, 45]