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

Gom·2021년 6월 3일
0

Algorithm

목록 보기
39/48
post-thumbnail

Bubble Sort

개념

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

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

과정

  1. 현재 원소가 다음 원소의 값보다 크면 그 두 원소를 바꾼다.
  2. 전체 원소 비교를 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]));

참고자료
CS50
https://medium.com/@peterlin5301997/bubble-sort-5a66156c942e
https://im-developer.tistory.com/133

profile
안 되는 이유보다 가능한 방법을 찾을래요

0개의 댓글