[알고리즘 with JS] 버블 정렬 (bubble sort)

버블 정렬은 오름차순 기준으로 정렬한다면 더 큰 숫자가 한 번에 하나씩 뒤로 가는 것이다.

루프를 돌면서 자신의 오른쪽 항목과 비교하고,
자신이 오른쪽 항목보다 크면 swap 하여 정렬한다.

그래서 루프 하나를 다 돌면 가장 큰 수가 오른쪽으로 정렬되어 반복할 때마다 정렬할 항목 줄어든다.

따라서 데이터가 거의 다 정렬된 상태에서 버블 정렬을 사용하면 좋다.

 

아래는 버블 정렬에서 가장 중요한 swap 코드이다.

function swap (arr, idx1, idx2) {
  let tmp = arr[idx1];
  arr[idx1] = arr[idx2];
  arr[idx2] = tmp;
}

// ES6 문법 구조 분해 할당을 사용해 교환
const swap = (arr, idx1, idx2) => {
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx2]];
}

아래는 배열의 처음부터 값을 비교해 나가는 버블 정렬 코드이다.

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]) {
        let tmp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = tmp;
      }
    }
  }
  return arr;
}

이 코드를 사용해 버블 정렬을 해도 값이 잘 나오지만, 처음부터 끝까지 다 비교하기 때문에
이미 정렬된 값들도 값을 비교하고 넘어간다는 단점이 있다.

 

따라서 맨 처음 for문을 0부터 시작하는 것이 아닌 배열 길이만큼 시작하여 하나씩 줄여가는 방식을 사용하였다.

function bubbleSort(arr) {
  let sorted;
  for (let i=arr.length; i>0; i--) {
    for (let j=0; j<i-1; j++) {
      sorted = true;
      if (arr[j] > arr[j+1]) {
        let tmp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = tmp;
        sorted = false;
      }
    }
    if (sorted) break;
  }
}

sorted는 해당 데이터가 정렬되어 있는지 체크해주는 변수이다.

이 변수를 사용해 sorted가 true면 swap이 일어나지 않은 것이므로
정렬되어 있다고 판단하여 break로 for문을 나가 불필요한 코드 실행을 줄일 수 있다.