버블 정렬 알고리즘

승훈·2022년 9월 22일
0

버블 정렬 알고리즘

정렬 알고리즘 중 첫번째 값을 모든 값들과 하나씩 다 비교하여 정렬을 하는 방법이다.

마치 거품이 일어나듯이 연쇄적으로 자기 자리를 찾아간다고 해서 버블 정렬이란 이름이 붙여졌다.
따라서 버블정렬의 특징은 n회차 돌때마다 오른쪽의 n번째 자리가 확정된다는 것이다.

Worst Case: O(n^2): 정렬이 하나도 안되어있는 경우

장점: 배열 내에서 정렬을 하기 때문에 메모리가 절약된다.

단점: worst case 처럼 n^2가 소요될 수 있기 때문에 배열 개수가 많아질 수 록 성능이 떨어진다.

function bubleSort(array) {
	// array 오름차순 정렬할 array
 
  for (let i=0; i < array.length; i++) {
  	let swap;
    for (let j =0; j < array.length-1-i; j++) {
      if (array[j] > array[j+1]) {
      	swap = array[j];
        array[j] = array[j+1];
        array[j+1] = swap;
      }
    }
    console.log(i + '회차: ', array);
    // swap 에 담긴 값이 없다면 정렬 완료 되었다는 뜻
    if (!swap) {
    	break;
    }
  }
  return array;
}

const testValue = bubleSort([5,3,1,9,3]);
console.log('testValue:', testValue);
  • 실무에서는 거의 적용되지 않는 알고리즘입니다.
    javascript를 주로 사용하는 저로써는 기본적으로 제공하는 sort() 메소드나 lodash의 sortBy() 메소드를 사용하는데요.
    하지만 제공하는 메소드를 무작정 사용하기 보다는 기본적으로 정렬 알고리즘을 인지해야 더 좋은 퍼포먼스를 낼 수 있다고 생각합니다.

cf)
1. 위 코드에서 사용했던 for문과 forEach의 차이
forEach는 읽기 전용임으로 배열의 수정이 불가하다.
2. sort() 메소드는 배열의 요소를 문자열로 캐스팅하여 순서를 매기는 메소드.
따라서 숫자를 비교할시 메소드 그대로 사용하지 못함.

var score = [4, 11, 2, 10, 3, 1]; 

/* 오류 */
score.sort(); // 1, 10, 11, 2, 3, 4 
              // ASCII 문자 순서로 정렬되어 숫자의 크기대로 나오지 않음

/* 정상 동작 */
score.sort(function(a, b) { // 오름차순
    return a - b;
    // 1, 2, 3, 4, 10, 11
});

score.sort(function(a, b) { // 내림차순
    return b - a;
    // 11, 10, 4, 3, 2, 1
});

0개의 댓글