버블정렬 (Bubble Sort_ JavaScript)

버블정렬 방식

• 앞에서 부터 데이터를 두개씩 비교해서 더 큰게 오른쪽으로 이동한다. 그렇게 처음부터 끝까지 한번 다 돌고나면 오른쪽 끝에는 가장 큰 데이터가 자리잡게 된다.
• n번째 정렬이 완료되면 뒤에서 n번째 자리가 확정되는 것이다.

장점

• 정렬이 잘 되어 있을수록 반복이 줄어들기 때문에 빠르게 정렬이 가능하다.
• 비교적 구현하기가 가장 쉬운 정렬방법이다.

단점

• 정렬이 안되어 있을수록 반복을 더 여러번 반복해야 하기때문에 오래 걸린다.
• 자료가 많을수록 정렬을 위한 시간이 오래 걸린다.

 

버블정렬 (JavaScript)

function bubbleSort(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}`);
        if(!swap){
            break;
        }
    }
    return array;
}
console.log(bubbleSort([5,2,3,1,4]));

 

for문으로 i가 0부터 array.length보다 작을 때까지 loop을 돌리고,

그 안에 j가 0부터 array.length - 1 - i보다 작을 때까지 loop을 돌린다.

array.length - 1 - i인 이유는 일단 array[j]와 array[j + 1]을 비교할 예정이기 때문에

배열의 마지막 데이터를 포함하지 않아도 검색 대상에 포함되므로 1을 빼줘야하고

두번째로 각 회전이 끝날 때마다 마지막 데이터의 정렬이 끝나기 때문에 i를 빼줘야한다.

 

이제 swap이란 변수를 만들어 array[j]와 array[j + 1]을 비교하여 array[j]가 더 크면 자리를 교환한다.

만약에 각 회전을 끝내고 swap 변수가 undefined상태라면 정렬이 다 되어있다는 뜻이므로 바로 for문을 종료시킨다.

 

출처: https://im-developer.tistory.com/133 [Code Playground]