자바스크립트 정렬 알고리즘 2 : Bubble Sort

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)

---

Bubble Sort, Insertion Sort, Selection Sort 이 세가지가 주요 정렬 알고리즘 중 가장 우선적으로 배울 정렬 알고리즘이다. Merge Sort와 Quick Sort는 앞선 세 개보다 조금 더 Advanced한, 복잡한 알고리즘이다. 뒤의 두 개는 앞선 세 개보다 더 효율적이다.

 

Bubble Sort의 작동 방식을 보면, 가장 구현하기에 간단하기는 하지만 가장 비효율적인 정렬 알고리즘이다. Average Case에서 Bubble Sort의 Big O는 O(n^2)이기 때문이다.

 

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function bubbleSort(array) {
  const length = array.length;
  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length; j++) { 
      if(array[j] > array[j+1]) {
        let temp = array[j]
        array[j] = array[j+1];
        array[j+1] = temp;
      }
    }        
  }
}

bubbleSort(numbers);
console.log(numbers);

코드를 보면 알 수 있듯이, for 문 안에 또 다시 for 문이 반복되는 nested for loop의 형태이기 때문에 O(n^2)이다.

 

☞ Bubble Sort의 로직