[2][알고리즘 - 정렬] 버블정렬(Bubble Sort)이란? javascript 구현

버블정렬이란?

 

서로 이웃한 데이터들을 비교하며

가장 큰 데이터를 가장 뒤로 보내며 정렬

하는 방식입니다.

 

출처 - https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

이모습이 꼭 버블같다고해서 붙여진 이름이라고 합니다.

 

 

정렬에 있어서 가장 기본이며

처음으로 배우는 정렬이라고 하니,

이를 통해 정렬의 사고력을 가져보자구요.

 

 

 

버블정렬의 동작 과정입니다.

 

위에서 말했듯

순차적으로 돌면서

2개씩 쌍으로 비교하여

가장 큰 값을 마지막으로 보내는 작업을

반복하여 수행합니다.

 

때문에,

배열의 크기에 따라 반복 수행되고,

그 안에서 한번더 배열의 크기에 따라

가장 큰 숫자를 마지막으로 밀어 넣는 작업을 합니다.

 

이를 간단하게 javascript로 구현해보겠습니다.

 

const arr = [7,5,9,1,3,2,4];

// 버블 정렬
const bubbleSort = (array) => {
    for (let i = 0; i < array.length - 1; i++) {
        for (let j = 0; j < array.length -i -1; j++) {
        	// 구조분해 할당을 통해 위치 교환
            if(array[j] > array[j+1]) [array[j], array[j+1]] = [array[j+1], array[j]];
        }
    }
};

console.log('arr=', arr);
// [7, 5, 9, 1, 3, 2, 4]

bubbleSort(arr);

console.log('arr=', arr);
// [1, 2, 3, 4, 5, 7, 9]

 

잘 확인하셨나요?

이처럼 버블 정렬은 for이 중첩으로 2개가 있기 떄문에

O(n^2) 의 시간복잡도를 평균적으로 나타냅니다.

 

확실히 입문 정렬이라 그런지

쉽게 이해할 수 있었습니다.

정렬을 한번 보고나니

어떻게 빠른 속도로 정렬을 시킬 수 있을지

궁금해집니다.

 

출처 - https://coding-factory.tistory.com/138

 

 

 

 

 

앞으로 알아볼 정렬들의

비교 표를 작성해봤습니다.

출처 - https://dev.to/mauriciord/do-you-know-what-is-big-o-notation-1hhp

 

이 그래프와 정렬 비교표는 지속적으로 계속 봐야 할 것 같습니다.