버블 정렬 (Bubble Sort)

[65, 73, 67, 98, 75, 80, 87, 30, 61, 45, 4, 36, 52, 5, 23, 68, 71, 70, 61, 21, 29, 73, 36, 90, 13,  97, 14, 71, 1, 51, 49, 3, 15, 64, 51, 87, 80, 8, 73, 84, 21, 93, 46, 87, 49, 41, 77, 40, 73, 96]

버블 정렬이란?

인접한 요소의 크기를 비교하는것을 반복

비교정렬

추가 메모리 x

 

시간복잡도

	시간 복잡도 (comparisons)	시간 복잡도 (swaps)
최악	O(n^2)	O(n^2)
평균	O(n^2)	O(n^2)
최상	O(n)	O(1)

최악의 경우 공간 복잡도

전체 O(n), 보조 O(1)

 

특징

구현 간단함

가장 왼쪽에서 오른쪽으로 이동시 모든 요소와 교환

요소가 최종위치에 이미 있더라도 교환이 일어날 수 있다

비효율적이라 잘 안씀

 

로직

이중 for문으로 인접요소 크기 비교해서 큰수를 뒤로 보냄

즉, 처음 순회때 가장 큰 수가 맨 뒤로 가며

두번째 순회때 두번째로 큰 수가 뒤에서 두번째로 간다 (오름차순의 경우)

 

코드

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

let arr = [
  65, 73, 67, 98, 75, 80, 87, 30, 61, 45, 4, 36, 52, 5, 23, 68, 71, 70, 61, 21, 29, 73, 36, 90, 13,
  97, 14, 71, 1, 51, 49, 3, 15, 64, 51, 87, 80, 8, 73, 84, 21, 93, 46, 87, 49, 41, 77, 40, 73, 96,
];

console.log(bubbleSort(arr));

// 결과
[
   1,  3,  4,  5,  8, 13, 14, 15, 21, 21, 23,
  29, 30, 36, 36, 40, 41, 45, 46, 49, 49, 51,
  51, 52, 61, 61, 64, 65, 67, 68, 70, 71, 71,
  73, 73, 73, 73, 75, 77, 80, 80, 84, 87, 87,
  87, 90, 93, 96, 97, 98
]
comparisons : 1105
swaps : 590

swapsCount를 이용해서

모두 정렬됐을 경우 더 이상 진행안되도록하면 성능이 향상된다