TIL 82 | 정렬(2) - JS로 Bubble Sort 구현

Gom·2021년 6월 3일

JavaScript Sort bubblesort

Algorithm

목록 보기

39/48

Bubble Sort

개념

두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 알고리즘

정렬 과정이 버블이 올라오는 듯하여 이러한 이름이 붙여졌다.

과정

현재 원소가 다음 원소의 값보다 크면 그 두 원소를 바꾼다.
전체 원소 비교를 1회 끝마치면 최소(or최대)값이 가장자리에 위치하게 되는데 2회차 비교 시에는 최소(or최대)값을 제외한 나머지 원소 범위 내에서 비교를 수행한다.

그 결과, 반복이 진행될수록 무시하는 범위가 커져 끝으로 갈수록 속도가 빨라진다.

시간복잡도

Big-O : O(n^2)

Big-Ω : Ω(n^2)

(n-1)*(n-2) = n^2-3n+2
정렬이 되어 있는지 여부에 관계 없이 루프를 돌며 비교를 해야 하므로 실행 시간 상하한이 동일하다.

장단점

장점

구현이 간단하고 소스코드가 직관적임.
메모리 절약 O(1)
정렬하고자 하는 배열 안에서 교환하는 방식으로 다른 메모리 공간 불필요
(in-place sorting 제자리정렬)

단점

시간복잡도 비효율적

특징

Stable

중복 데이터가 있는 경우 데이터가 교환되지 않고 정렬이 다 끝난 후에도 기존 중복 데이터의 순서가 유지되는 정렬

코드

function bubbleSort (array) {
  for(let i=0; i<array.length; i++){
    let swap;
    for(let j=0; j<array.length-1-i; j++){
      if(array[j]>array[j+1]){
        swap = array[j];
        array[j] = array[j+1];
        array[j+1] = swap;
      }
    }
    console.log(`${i}회전 : ${array}`)
    if(!swap){
      break;
    }
  }
  return array;
}
console.log(bubbleSort([5,7,3,4,1,6,2]));