버블소트

버블소트

마치 버블같이 연쇄적으로 앞뒤값을 비교해서 자리를 찾아 나간다는 점에서 버블소트라는 이름이 붙었다. 예를 들어

let arr = [5,4,3,2,1] 

라는 배열이 있다면 두개씩 짝을 지어서 비교해 나가며 두개의 앞에 있는 수가 더이상 뒤 보다 크지 않을때까지 바꿔 나간다.

1회전 첫번째는 5와 4를 비교해서 앞에 것이 크기 때문에 바꾼다. 그러면

let arr = [4,5,3,2,1] 

가 되며 또 5와 3을 비교한다. 그래서 마찬가지로 바꾸면

let arr = [4,3,5,2,1] 

가 되며 또 5와 2를 비교하며 또 바꾸고 바꾸면 최종적으로

let arr = [4,3,2,1,5]

가 된다. 이렇게 1회전이 끝난다.

2회전째는

let arr = [4,3,2,1,5]

4와 3을 제일 처음에 비교하기 시작하며 마지막 회전이 완료된 5는 비교 할 필요가 없다.

그래서 2회전은

let arr = [3,2,1,4,5]

가 된다.

3회전

let arr = [2,1,3,4,5]

.....

마지막 회전

let arr = [1,2,3,4,5]

가 된다.

이렇다 보니 비교 횟수가 하나씩 줄어 든다는 점이 장점이다. 단점은 비교대상 즉 원소의 갯수가 많아 지면 성능이 저하 된다. 시간복잡도 역시 O(n^2)으로 데이터가 많을시 성능저하가 뚜렷하다고 볼 수 있다.

코드

const bubbleSort = (arr) => {
  for (let i = 0; i <= arr.length - 1; i++) {
    let temp;
    for (let j = 0; j <= arr.length - 1 - i; j++) {//=> 이부분이 이미 소트가 완료된 엘리먼트를 비교 대상에서 줄이는 것이다.
      console.log(`${i}바퀴`, arr[j], arr[j + 1]);
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
};