거품 정렬(Bubble Sort)

거품 정렬(Bubble Sort)

• 인접한 두 값을 검사하여 정렬하는 알고리즘
• 두 값이 순서대로 되어 있지 않으면 서로 교환

시간 복잡도 : O(n^2)   => n(n-1)/2

공간 복잡도 : O(N)

 

장점

• 구현이 간단하고 가독성이 좋다
• 다른 메모리 공간이 필요하지 않다
• 안정적인 정렬이다

단점

• 시간 복잡도가 최선, 최악 모두 O(N^2)이여서 비효율적이다
• 교환 횟수가 많다

function bubbleSort(arr) {
  var temp = 0; // 교환할때 필요한 변수
  var count = 0; // 시간복잡도 계산용 변수
  for(var i=0; i<arr.length; i++) {
    for(var j=0; j<arr.length-1-i; j++) {
      count++
      console.log(`${arr}, i : ${i}, j : ${j}, 횟수 : ${count}`)
      if(arr[j] > arr[j+1]) {
        temp = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = temp
      }
    }
  }
  return arr
}

console.log(bubbleSort([4,10,3,2,6]))

// 4,10,3,2,6, i : 0, j : 0, 횟수 : 1
// 4,10,3,2,6, i : 0, j : 1, 횟수 : 2
// 4,3,10,2,6, i : 0, j : 2, 횟수 : 3
// 4,3,2,10,6, i : 0, j : 3, 횟수 : 4
// 4,3,2,6,10, i : 1, j : 0, 횟수 : 5
// 3,4,2,6,10, i : 1, j : 1, 횟수 : 6
// 3,2,4,6,10, i : 1, j : 2, 횟수 : 7
// 3,2,4,6,10, i : 2, j : 0, 횟수 : 8
// 2,3,4,6,10, i : 2, j : 1, 횟수 : 9
// 2,3,4,6,10, i : 3, j : 0, 횟수 : 10
// [ 2, 3, 4, 6, 10 ]