[JavaScript] 정렬 (2) 거품 정렬

거품 정렬

거품정렬은 가장 간단한 정렬 알고리즘이다. 거품 정렬은 전체 배열을 순회하면서 항목이 다른 항목보다 큰 경우 두 항목을 교환하는 방식이다. 이 방식이 거품이 밀려 올라가는 것과 같은 모습이라고 해서 거품 정렬이라는 이름이 붙여졌다. 아래는 거품 정렬의 코드이다.

// swap 함수는 두 배열의 인덱스의 값을 바꾸는 함수임.
const swap = (array, index1, index2) => {
  let temp = array[index1]; // 바뀔 것을 대비하여 값 저장
  array[index1] = array[index2];
  array[index2] = temp;
}

const bubblesort = array => {
  for (let i=0;i<array.length;i++) {
    for (let j=0;j<=i;j++) {
      if (array[i] < array[j]) {
        swap(array,i,j)
      }
    }
  }
  return array;
}

이 코드의 가장 큰 문제점은 배열의 거의 모든 짝을 비교해서 비효율적이라는 것이다. 게다가 시간복잡도가 O(n^2)이기 때문에 배열의 양이 많아질수록 시간이 기하급수적으로 증가한다. 따라서 이미 정렬이 되어있는 경우에는 반복을 멈추는 작업을 추가하면 좋다. 아래는 효율적 거품 정렬이다. break를 걸기 위하여 코드를 살짝 수정하였다.

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

const bubbleSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  for (let i=0;i<arr.length;i++) {
    let swaps = 0;
    for (let j=0;j < arr.length - 1 - i;j++) {
      if (arr[j] > arr[j+1]) {
        swaps++
        swap(j,j+1,arr)
      }
    }
    if (swaps === 0) break;
  }
  return arr
};


const arr = [1, 2, 21, 43, 100, 100, 82, 6]
console.log(bubblesort(arr));