[자료구조] 버블 정렬

자료구조의 기본 알고리즘

 

" 버블정렬 "

 

구현이 간단하고 쉬운 정렬부터 하다보니, 여전히 성능에서는 많이 떨어지는 경향이 있네요.

 

 

버블정렬이란, 맨 앞 2개 데이터씩 비교하면서 작은 수를 한 칸씩 앞으로 당겨오는 것을 말해요. 계속 당겨오는 것을 반복하면서 데이터 개 수만큼 반복하면 어느새 정렬이 되어있게되죠 :-)

 

그래서 시간복잡도는 O(n²)

 

 

그림을 보면서 이해하도록 하죠 :)

 

 

 

이렇게 한 바퀴를 돌면 가장 큰 수인 [4]가 맨 뒤로 정렬되게 되죠.

그럼 이 규칙을 확인해보면, 한 바퀴 돌때마다 가장 큰 수가 맨뒤로 정렬되는 규칙이 확인했구요!

 

그렇다면 다음번 비교할 때는 맨 마지막 값을 하나씩 빼면서 비교하면 되겠군요!?

 

이런 규칙을 통해서 최종 정렬 결과는 [ 1, 2, 3, 4 ] 가 나오겠죠?

그럼 소스 구현을 해보고 결과를 확인해볼까요 : ) 

 

function BubbleSort(data) {
    let temp;
    for (let count = 0; count < data.length - 1; count++) {
        for (let i = 0; i < data.length - 1 - count; i++) {
            if (data[i] > data[i + 1]) {
                temp = data[i];
                data[i] = data[i + 1];
                data[i + 1] = temp;
            }
        }
    }
    return data;
}
var data = [3, 5, 7, 89, 2, 46, 76, 43, 34, 6, 7, 57, 45, 2, 2, 8, 89, 7, 100];
console.log(BubbleSort(data));

 

 

버블정렬도 쉽네요.

대학교때 공부할 땐 엄청 어렵게 느꼈었는데 지금보니 별거없네요 

 

어렵다고 느껴지시는 분들은 ! 하다보면 어느순간 쉽다고 느끼실거에요 

화이팅할게요 : - )