Bubble Sort

 

참고 : 버블정렬(Bubble Sort)

 

목차

정렬 알고리즘 소개
기본 내장 자바스크립트 정렬
버블 정렬 : 개요
버블 정렬 : 구현
버블 정렬 : 최적화
버블 정렬 : 빅오 복잡도

 

 

정렬 알고리즘 소개

슬라이드

정렬알고리즘 애니메이션

 

목표1. Bubble Sort2. Selectrion Sort3. Insertion Sort

기본 내장 자바스크립트 정렬

JS  - Array.prototype.sort()
실행 과정
1. 옵셔널한 비교 함수를 인자로 받는다. (없어도 됨)
2. 비교함수에는 JS에게 어떻게 쓸것인지 써줘야한다.
3. 비교요소는 a 와 b같은 요소 쌍으로 이루어져 있다. 그리고 반환 값에 따른 비교 순서를 결정한다.
  3-1. 만약 음수 값이 반환 되면,  a -> b 순서가 된다.
  3-2. 만약 양수 값이 반환 되면,  b -> a 순서가 된다.
  3-3. 만약 0 이 반환 되면,  a와 b는 똑같은 값이다.

 

 

버블 정렬 : 개요

VisualgoSorting

 

버블정렬 의사코드
1. 배열의 끝 인덱스를 i라는 변수를 사용하여 처음부터 루프를 시작한다.
2. 처음부터 i - 1까지 j라는 변수로 내부 루프를 시작한다.
3. arr[j]가 arr[j+1]보다 크면 이 두 값을 바꾼다!
4. 정렬된 배열을 리턴한다.

 

버블 정렬 : 구현 🎁

// UNOPTIMIZED VERSION OF BUBBLE SORT
function bubbleSort(arr){
  for(var i = arr.length; i > 0; i--){		// 실행 횟수: 8번(배열인자 개수)
    for(var j = 0; j < i - 1; j++){		// 비교 횟수 : 7->6->5->...->1번(1회씩 감소)
      console.log(arr, arr[j], arr[j+1]);
      if(arr[j] > arr[j+1]){			//a 와 b 비교 후 a가 크면 a,b 스와이프
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;         
      }
    }
  }
  return arr;
}

// ES2015 Version
function bubbleSort(arr) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };

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

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

 

 

버블 정렬 : 최적화

더 이상 스왑 할게 없다면 외부 반복문 종료

// Optimized BubbleSort with noSwaps
function bubbleSort(arr){
  var noSwaps;
  for(var i = arr.length; i > 0; i--){
    noSwaps = true;		// ① 계속 true로 설정
    for(var j = 0; j < i - 1; j++){
      if(arr[j] > arr[j+1]){
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
        noSwaps = false;		// ③ swap 한다면 noSwap을 false로 만듦 -> 반복문 종료안함
      }
    }
    if(noSwaps) break;		// ② true면 반복문 종료
  }
  return arr;
}

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

 

 

버블 정렬 : 빅오 복잡도

O(n²) - Worst, Average

O(n) - Best