[Algorithm][JavaScript] 버블 정렬(Bubble Sort)

버블 정렬이란?

서로 인접하는 두 원소를 비교하여 정렬하는 알고리즘입니다.

만약 n번째 요소가 n+1번째 요소보다 크다면, 두 요소의 위치를 바꿉니다.

이 교환 작업을 반복하면 가장 큰 요소가 마지막에 위치하게 됩니다.

앞의 작업들을 배열의 크기만큼 반복하면 오름차순 정렬이 됩니다.

내림차순 정렬을 하기 위해서는 반대로 수행하면 됩니다.

 

버블 정렬 구현

const bubbleSort = function (arr) {

  let checkArea = arr.length-1; // swap 범위

  for(let i=0; i<arr.length; i++){

    for(let j=0; j<checkArea; j++){      

      if(arr[j] > arr[j+1]){ // 앞의 원소가 더 크면 swap

        let val = arr[j+1]

        arr[j+1] = arr[j];

        arr[j] = val;

      }

    }

  }

  return arr;

};

let result = bubbleSort([2, 1, 3, 6, 5, 8, 105, 55, 74, 22, 25, 26, 44, 7]);

console.log(result); // 182번 반복

배열은 오름차순으로 잘 정렬이 됩니다.

위 코드를 실행하면 총 182번의 반복을 수행합니다.

182번에는 수행할 필요가 없는 부분이 포함되어 있습니다.

이 부분을 제거해 수행 시간 단축이 필요합니다.

 

버블 정렬 구현 - 수행 시간 단축 1

const bubbleSort = function (arr) {

  let checkArea = arr.length-1; // swap 범위

  for(let i=0; i<arr.length; i++){

    for(let j=0; j<checkArea; j++){      

      if(arr[j] > arr[j+1]){ // 앞의 원소가 더 크면 swap

        let val = arr[j+1]

        arr[j+1] = arr[j];

        arr[j] = val;

      }

    }

    checkArea--;

  }

  return arr;

};

let result = bubbleSort([2, 1, 3, 6, 5, 8, 105, 55, 74, 22, 25, 26, 44, 7]);

console.log(result); // 91번 반복

swap을 통해 가장 큰 요소가 마지막에 위치하면 더 이상 마지막 요소와 비교할 필요가 없습니다.

이 부분을 제거하면 수행 시간을 단축할 수 있습니다.

 

버블 정렬 구현 - 수행 시간 단축 2

const bubbleSort = function (arr) {

  let checkArea = arr.length-1; // swap 범위

  for(let i=0; i<arr.length; i++){

    let flag = false; // 원소 swap 유무 체크

    for(let j=0; j<checkArea; j++){      

      if(arr[j] > arr[j+1]){ // 앞의 원소가 더 크면 swap

        let val = arr[j+1]

        arr[j+1] = arr[j];

        arr[j] = val;

        flag = true //원소 swap이 있으면 true

      }

    }

    if(flag === false){ // 원소 swap이 한 번도 없으면 break

      break;

    }

    checkArea--;

  }

  return arr;

};

let result = bubbleSort([2, 1, 3, 6, 5, 8, 105, 55, 74, 22, 25, 26, 44, 7]);

console.log(result); // 81번 반복

반복을 전부 수행하기 전에 배열의 정렬이 완료된다면 더 이상 반복을 수행할 필요가 없습니다.

flag라는 변수를 이용해 swap의 발생 유무를 확인해 정렬이 완료되면 반복을 종료합니다.

 

시간 복잡도

BEST	AVERAGE	WORST
O(n^2)	O(n^2)	O(n^2)

 

버블 정렬의 장단점

장점

• 구현이 쉬움

 

단점

• 최종 결과에 맞는 위치에 있는 요소도 교환, 비교 연산이 일어남