[Algorithm]버블 정렬(Bubble Sort)

velgmzz·2022년 12월 22일
0

Algorithm

목록 보기
2/4
post-thumbnail

버블 정렬?

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않으면 자리를 교환하면서 정렬하는 알고리즘이다.

Sorting Algorithm Animations // 정렬되지않은 데이터를 Animation으로 다양하게 볼 수 있다.

알고리즘 과정

1회전에 첫 번째 원소와 두 번째 원소를 비교하고 첫 번째 > 두 번째라면 서로 교환한다. 첫 번째 원소가 두 번째 원소와 같거나 작다면 교환하지 않고 진행한다. 다시 두 번째 원소와 세 번째 원소, 세 번째 원소와 네 번째 원소, ... 같은 방법으로 length - 1 번째 원소까지 비교하여 조건에 맞으면 교환한다.

1회전을 수행하고 나면 제일 큰 원소는 마지막으로 이동하고 정렬에서 제외된다. 이때 첫 번째 원소부터 다시 시작한다. 2회전을 수행하고 나면 끝에서 두 번째 원소까지 정렬에서 제외되고 이 과정을 반복하여 모든 데이터를 정렬한다.

알고리즘 구현

function bubble(arr) {
  for(let i = 0; i < arr.length; i++) {
    for(let j = 0; j < arr.length; j++) {
      if( arr[j] > arr[j+1] ) {
        let temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
  return arr;
}

설명과 GIF를 보면 정렬된 원소는 제외하고 남은 원소들로만 다시 정렬을 해야한다.
위와 같이 구현하면 문제점이 발생한다. 1회전 수행 후 이미 정렬된 원소를 계속하여 비교하는 점, length의 범위를 넘어가 마지막 원소와 undefined를 비교하는 점이다.

또 한가지가 더 있는데, [5, 1, 2, 3, 4]와 같이 거의 정렬된 데이터에서 1회전 수행 후 정렬이 끝나지만 다시 여러번 비교하며 교환없이 수행된다.

최적화

function bubble( arr ) {
  let noSwaps;
  for ( let i = arr.length; i > 0; i-- ){
    noSwaps = true;
    for ( let j = 0; j < i-1; j++ ){
      if ( arr[j] > arr[j+1] ) {
        let temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
        noSwaps = false;
      }
    }
    if ( noSwaps ) break;
  }
  return arr;
}
profile
정리하며 공부하는 블로그, React/Next를 공부합니다

0개의 댓글