Algorithm [정렬 : 버블정렬(bubbleSort)]

버블 정렬이란?

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
• 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
• 선택 정렬과 기본 개념이 유사하다.

 

버블 정렬(bubble sort) 알고리즘의 구체적인 개념

버블 정렬은

첫 번째 자료와 두 번째 자료를,

두 번째 자료와 세 번째 자료를,

세 번째와 네 번째를, …

 

이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.

1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 

2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 

2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 

이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

 

console의 결과를 보면 내용을 바로 알수 있습니다.

function bubbleSort(arr) {
  const Len = arr.length;

  for (let i = 0; i < Len - 1; i++) {
    for (let j = 0; j < Len - 1 - i; j++) {
      console.log('i:', i);
      console.log('j:', j);
      console.log('arr[j]:', arr[j]);
      console.log('arr[j+1]:', arr[j + 1]);
      console.log('arr:', arr);
      if (arr[j] > arr[j + 1]) {
        console.log('정렬해야함');
        swap(j, j + 1, arr);
        console.log('arr:', arr);
      }
      console.log();
    }
  }

  return arr;
}

let result = bubbleSort([3, 2, 5, 1]);
console.log(result);

출력

 

 

버블 정렬(bubble sort) 알고리즘의 예제

일반적인 코드

// naive solution
function bubbleSort(arr) {
  const Len = arr.length;

  for (let i = 0; i < Len - 1; i++) {
    // 매 반복(iteration)마다 i번째로 큰 수가 마지막에서 i번째 위치
    // 이미 정렬된 요소는 고려할 필요가 없으므로, 'j < Len - 1 - i'만 비교
    for (let j = 0; j < Len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(j, j + 1, arr);
      }
    }
  }

  return arr;
}

function swap(idx1, idx2, arr) {
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}

단점 

 - 이미 정렬되어 있어도 끝까지 코드를 진행 시킴

 

최적화 풀이

// optimized solution
function bubbleSort(arr) {
  const Len = arr.length;

  for (let i = 0; i < Len; i++) {
    // swap 횟수를 기록
    // 어떤 요소도 swap되지 않은 경우, 배열은 정렬된 상태
    let swaps = 0;

    // 매 반복(iteration)마다 i번째로 큰 수가 마지막에서 i번째 위치
    // 이미 정렬된 요소는 고려할 필요가 없으므로, 'j < N - 1 - i'만 비교
    for (let j = 0; j < Len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swaps++;
        swap(j, j + 1, arr);
      }
    }

    if (swaps === 0) {
      break;
    }
  }

  return arr;
}