거품 정렬

거품정렬

• 가장 간단한 알고리즘
• 전체 배열을 순회하면서 항복이 다른 항복보다 큰 경우, 두 항목을 교환
• 시간복잡도 O(n^2), 공간복잡도 O(1)
• 단점
  • 최악의 종류의 정렬
  • 다른 정렬 알고리즘은 배열의 이미 정렬된 부분을 활용하는데 비해 거품 정렬은 모든 가능한 짝을 비교하기 때문
  • 중철 루프를 사용하기 때문에 시간복잡도는 위와 같다.
    

코드 구현

const swap = (arr, idx1, idx2) => {
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}

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

bubbleSort([6,1,2,3,4,5]); // [1,2,3,4,5,6,]