[인프런] 버블 정렬 - JavaScript

버블 정렬 (Bubble Sort)

두 인접한 원소를 검사하여 정렬하는 방법

1. 배열의 첫번째 요소와 두번째 요소의 값을 비교한다.
2. 오름차순으로 정렬해야 할 경우 첫번째 요소의 값이 더 크면 두 요소의 값을 교환한다. (내림차순일 경우 첫번째 요소의 값이 더 작으면 두 요소의 값을 교환한다.)
3. 비교하는 배열의 첨자(요소의 번호, 위치)를 하나씩 증가하여 1, 2번을 반복한다.
4. 배열의 마지막 요소까지 비교했으면 1번부터 다시 반복한다.

n번째 회전이 끝날 때마다 (배열 요소의 갯수 - n)번째 데이터의 위치가 정해진다.

Big O

장점

• 알고리즘이 단순하다

단점

• 비교 작업이 많아 연산 시간이 오래 걸린다

코드

인프런 '자바스크립트 알고리즘 문제풀이' 섹션7 버블 정렬 강의 참고

function solution(arr) {
  let answer = arr;

  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return answer;
}

let arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr)); // [ 5, 7, 11, 13, 15, 23 ]

참고
거품 정렬 - 위키백과
[알고리즘] 버블 정렬 - 냐쨩의 포트폴리오
[버블 정렬 best case 시간복잡도] 진화한 버블 정렬, 완전히 정렬되었을 때 best case O(n)?