버블 정렬

Goal

1. 버블 정렬의 정렬 방식
2. 버블 정렬의 특징
3. javascript 구현
4. 시간 복잡도

버블 정렬의 개념

인접한 두 개의 원소를 대소 비교하여 정렬하는 알고리즘

버블 정렬 예제

버블 정렬 javascript 구현 (오름 차순)

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

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

console.log(bubbleSort(numbers));  // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

버블 정렬의 시간 복잡도

이미 모두 정렬이 되어있는 상태에서는 O(N)의 시간복잡도를 가지지만
최악의 경우 O(N^2)의 시간복잡도를 가진다.