[Exchange Sort] 버블 정렬 (Bubble Sort)

정렬 알고리즘 위키

복잡도

• 최악 시간복잡도

  • $O(n^2)$ 비교, $O(n^2)$ 교환

• 최선 시간복잡도

  • $O(n)$ 비교, $O(1)$ 교환

• 평균 시간복잡도

  • $O(n^2)$ 비교, $O(n^2)$ 교환

• 공간복잡도

  • $O(1)$ 보조

구현 코드

export const arr = [
  14, 17, 12, 20, 1, 5, 9, 7, 3, 8, 6, 2, 4, 10, 11, 16, 15, 19, 18, 13,
];

import { arr } from "./number_array";

class bubbleSort {
  public static main(arr: number[]): void {
    let temp = 0;

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

      console.log(arr.toString(), `→ [${i}회]`);
    }
  }
}

bubbleSort.main(arr);