[알고리즘 JS] 버블 정렬 알고리즘 : Bubble Sort Algorithm

버블 정렬 알고리즘이란?

• 아래 그림의 주황색 부분 처럼, 인접한 두 개의 요소의 대소를 비교해 자리를 바꿔 정렬을 하는 알고리즘이다.
• 바깥쪽 반복과 안쪽 반복이 있을 때 바깥 반복을 배열의 길이만큼 반복하고, 안쪽 반복에서는 j로 0번째 인덱스부터 마지막요소를 제외한 범위만큼 반복하면서, 배열의 j번째 요소와 j + 1번째 요소의 대소를 비교한다. j + 1번째 요소와 비교되기 때문에 배열의 마지막 요소는 범위에 추가를 하지 않아도 저절로 반복이 된다. 

출처 : https://technologystrive.com/bubble-sort/

• 위 그림처럼 정렬이 완료된 범위의 마지막 부분은 정렬 범위에서 제외시켜 주어도 되는데, 그렇게 하기 위해서 i 가 증가할 때마다 j의 범위에서 i만큼 감소시켜준다. 

버블 정렬 알고리즘 코드 적용

const bubbleSort = function (arr) {
  for (let i = 0; i < arr.length - 1; i++) {
  // 매 반복마다 j 의 범위를 i 만큼 줄여나간다. (이미 정렬된 부분이기 때문에.)
    for (let j = 0; j < arr.length - i - 1; j++) {
    // 대소 비교를 하여 j 요소가 더 클 경우 swap 한다.
      if (arr[j] > arr[j + 1]) {
        let tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
  }
  return arr;
};

버블 정렬 알고리즘 최적화

• 기존 방식의 버블 정렬은 정렬이 완료가 된 시점이어도 반복을 계속 하기 때문에 그리 효율적이지 못하다. 따라서 이미 정렬이 완료된 시점이 될 경우, 즉 swap이 한번도 일어나지 않은 경우 정렬 알고리즘을 중단할 수 있다.
• 코드는 아래와 같다.

const bubbleSortOptimized = arr => {
  const N = arr.length;
  // 전체 길이만큼 i 를 반복한다.
  for (let i = 0; i < N; i++) {
    // swap 여부를 확인하기 위해 swap 변수에 false를 할당해준다.
    let swap = false;

    // 기존 버블 정렬과 동일하게 범위를 N에서 i 와 -1 만큼을 빼면서 j를 반복한다.
    for (let j = 0; j < N - i - 1; j++) {
      // 오름차순 정렬일 때, j가 j + 1 보다 작으면 위치를 바꾼다(swap)
      if (arr[j] > arr[j + 1]) {
        let tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
        // swap 변수를 true 로 재할당한다.
        swap = true;
      }
    }

    // 만약 swap 이 일어나지 않아서, 여전히 swap 이 false 인 경우 반복문을 탈출한다.
    if (!swap) break;
  }

  return arr;
};