[인프런] 버블 정렬 - JavaScript

이은빈 EUNBIN·2021년 7월 14일
0
post-thumbnail

버블 정렬 (Bubble Sort)

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

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

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



Big O

최악(Worst)
: 정렬이 하나도 안돼있는 경우
최선(Best)
: 이미 정렬이 돼있는 경우
평균(Avg)
O(n2)O(n)O(n2)



장점

  • 알고리즘이 단순하다



단점

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



코드

인프런 '자바스크립트 알고리즘 문제풀이' 섹션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)?

profile
Frontend Engineer & Value Creator

0개의 댓글