algorithm

자바스크립트로 구현한 버블정렬 알고리즘 (bubble sort in javascript)

버블 정렬 알고리즘이란?

버블 정렬 알고리즘은 정렬하는 형태가 버블과 비슷하다고 해서 붙여진 이름이다. 내부 구조를 살펴보면 순차적으로 바로 옆에 있는 데이터와 비교해서 옆의 데이터가 더 크면 자신과 위치를 교환한다. 즉, 첫 번째 데이터가 가장 크다면 계속 옆에 있는 데이터와 자리를 교환하며 해당 데이터는 맨 끝으로 이동하게 된다.이러한 형태가 마치 버블이 보글보글 올라가는 것과 비슷해 보여서 버블 정렬이라고 부른다.

성능

버블 정렬 알고리즘은 빅오 표기법으로 표시하면 O(N2)의 시간복잡도를 가지고 있다.

자바스크립트로 구현

function bubbleSort(arr) {
	let result = [...arr]; // 원본 데이터 복사
  
    for (let i = 0; i < result.length - 1; i++) {
        for (let j = 0; j < result.length - i; j++) {
            if (result[j] > result[j + 1]) {
                let temp = result[j];
                result[j] = result[j+1];
                result[j+1] = temp;
            }
        }
    }
    
    return result;
}

let items = [8,4,9,2,5,10,15,22,88,63,18];
bubbleSort(items); // [2, 4, 5, 8, 9, 10, 15, 18, 22, 63, 88]