Bubble Sort 알고리즘 및 최적화

Dorito·2022년 9월 26일
0

기초공사

목록 보기
6/6

Bubble Sort

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

console.log(bubbleSort([3, 6, 1, 8, 20]));

만약 전체 배열내 인지 개수가 n 개라면 루프 돌면서 n, n - 1, n - 2 ... 1 진행됨
따라서 n(n-1)/2, 즉 O(n2)O(n^2) 만큼의 시간 복잡도를 가진다

temp로 저장하는 식으로 구현한 부분을 동적할당으로 리팩토링했다. (뿌듯)

이미 정렬되어있는 경우, 루프를 취소하고 빠져나오도록 알고리즘 최적화

참고 사이트 https://nyajjyang-portfolio.tistory.com/17

swap이 진행되지 않은 경우, if break 문으로 바로 루프를 끝내고 다음 루프를 돌도록 구현하면 된다.

const OptimizationBubbleSort = (arr) => {
  const start = Date.now();
  const length = arr.length;
  for (let i = 0; i < length; i++) {
    let swapped = false;
    for (let j = i + 1; j < length; j++) {
      if (arr[i] > arr[j]) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        swapped = true;
      }
      if (!swapped) break;
    }
  }
  const end = Date.now();
  console.log(`Execution time at optimized Bubble Sort ${end - start} ms`);
  return arr;
};

const bubbleSort = (arr) => {
  const start = Date.now();
  const length = arr.length;
  for (let i = 0; i < length; i++) {
    for (let j = i + 1; j < length; j++) {
      if (arr[i] > arr[j]) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
  }
  const end = Date.now();
  console.log(`Execution time at Bubble Sort ${end - start}ms`);
  return arr;
};


let a = [];
for (let i = 1; i < 100000; i++) {
  a.push(i);
}

console.log(OptimizationBubbleSort(a));
console.log(bubbleSort(a));

비교해보면 최적화한 버블정렬은 2ms밖에 안나는데,
최적화하지 않은 정렬은 루프를 끝내지않고 하나하나 비교하면서 다 돌기 때문에 10156ms 이나 걸린다. (시간 차이가 엄청나다!)

1개의 댓글

comment-user-thumbnail
2023년 10월 22일

if (!swapped) break;의 스코프를 첫 번째 for문으로 옮기면 더욱 효율적으로 최적화할 수 있을 것 같아요.
만약 정렬되어 있는 배열이라면, i = 0인 루프 한 번만 돌았을 때 모든 정렬이 끝나면서 O(n)의 시간복잡도를 가질 수 있으니까요!

답글 달기