01.bubble-sort.md

Bubble Sort

본 내용은 뇌를 자극하는 알고리즘 (한빛미디어) 책을 공부하면서 정리한 내용입니다.

구현이 간단하고 버그를 만들 가능석이 적은 알고리즘. 하지만 실제로는 성능이 좋지 않기에 사용하지 않는다.

Description

• 앞뒤로 위치한 요소 간의 정렬을 진행한다.

  • 오름차순, 내림차순 등의 비교에 해당되도록 앞뒤 요소 간의 위치를 바꿔준다.

  • 회차가 끝나면 가장 마지막에 위치한 내용을 제외하고 다음 회차로 넘어가게 된다.

  • 즉, n개의 범위를 정렬하려면, (n-1)만큼 반복을 해야한다.

  • n(n-1)/2의 횟수의 비교를 진행해야한다. 예) 6개의 비교대상이 있으면 6(6-1)/2 = 15번의 비교가 필요

• 더이상 비교가 필요 없는 상황이 와도 계속 비교를 진행.

ex) [5] [1] [6] [4] [2] [3]

1st round: [1] [5] [4] [2] [3] [6] -> 5번의 비교

2nd round: [1] [4] [2] [3] [5] | [6] -> 4번의 비교

3rd round: [1] [2] [3] [4] | [5] [6]  -> 3번의 비교

4th round: [1] [2] [3] | [4] [5] [6]  -> 2번의 비교

5th round: [1] [2] | [3] [4] [5] [6]  -> 1번의 비교

• 3라운드에서 이미 정렬이 끝났지만 계속 해서 정렬을 위한 비교가 진행된다.

Code

const array = [5, 1, 6, 4, 2, 3, 10, 7, 9, 8];

const bubbleSort = array => {
  let length = array.length;

  for (let i = 1; i <= length - 1; i++) {
    // n-1, n-2, n-3...에서 증가되는 숫자를 나타냄
    console.log('총 비교 횟수', length - i);
    for (let j = 1; j <= length - i; j++) {
      // 총 비교하는 횟수만큼 반복해서 처리
      let temp;
      if (array[j] > array[j + 1]) {
        temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  console.log(array);
};

bubbleSort(array);