Algorithm - 버블정렬(Bubble Sort)

버블정렬이란?

두 인접한 데이터를 비교하여, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 알고리즘

Image Alt 텍스트

https://visualgo.net/ko/sorting을 참고하면 영상으로 볼 수 있다.

맨 앞에 두 수를 비교하여 앞에 데이터가 크면 뒤에랑 바꾸면서 한 칸씩 뒤로 가는 알고리즘이다.
회전을 한번씩 끝내면 마지막 비교했던 끝에 수는 제일 큰 수가 된다.
즉, n번째 회차가 끝나면 뒤에서 n번째 자리의 데이터가 확정된다. 마지막 비교한 수는 다음 회전에 비교하지 않아도 된다.

JavaScript

function bubbleSort (arr) {
  const length = arr.length;
  let temp;

  for (let i = 0; i < length - 1; i++) {
    for (let j = 0; j < length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) { // 앞의 수가 뒤에 수보다 크면
        temp = arr[j]; // 두 수를 바꿔준다
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }

    if (!temp) {
        break;
    }
  }
  return arr;
}

console.log(bubbleSort([6,4,3,1,2])); // 1,2,3,4,6

첫 번째 for문은 배열의 값을 순차적으로 비교하기 위한 for문이다.
두 번째 for문은 첫번째 for문의 숫자와 나머지 숫자를 비교하기 위한 for문이다.
length - 1 - i에서 -i를 해주는 이유는 마지막 숫자는 확정이 되어서 비교할 필요가 없기 때문에 첫번째 for문의 i 만큼 빼주는 것이다.
if (!temp)를 통해 바꿔준 게 없으면 break하여 끝내준다. (완전정렬)