[Udemy] 버블 정렬(bubble sort)이란 ?

정의

버블정렬은 오름차순 정렬 시 두 숫자를 비교해서 더 큰 숫자를 한번에 한칸씩 오른쪽으로 이동시키는 정렬이다.

 

접근

1. i 변수를 선언하여 반복문을 순회한다. 이 때, 순회 순서는 역순으로 한다.

2. j 변수를 선언하여 처음부터 i - 1 까지 순회한다.

3. 오름차순 정렬이라면 arr[j] > arr[j+1] 을 만족하면 서로의 위치를 교환한다.

 

코드

function bubbleSort(arr) {
    for (let i = arr.length; i > 0; i--) {
        for (let j = 0; j < i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}

 

i 변수의 반복문을 역순으로 한 이유는 최적화 때문이다.

첫번째 순회 때 마지막 요소까지 비교해야하므로 배열의 길이까지 순회하고,

두번째 순회 때 마지막 요소는 이미 정렬된 요소이므로 해당 요소의 비교는 제외해도 된다.

이런 식으로 하나씩 정렬이 완료될 때마다 비교하는 반복문의 길이를 줄여나가면 최적화를 할 수 있다.

 

최적화 코드

만약 거의 정렬된 배열을 넣었을 경우에는 결과가 어떨지 확인해보자.

위 코드에 j 변수 반복문에 console을 찍어서 배열과 비교하는 두 요소를 확인해본다.

input : [8, 1, 2, 3, 4, 5, 6, 7]

1,2 / 2,3 / 3,4 / 4,5 / 5,6 / 6,7 비교해서 swap(교환)이 일어나지 않았으므로

이 다음 반복문 또한 교환이 일어나지 않는것을 알 수 있다.

 

이를 토대로 swap 유무에 따라 swap이 발생하지 않은 j 반복문이 존재한다면

이후의 i 반복문을 탈출하는 코드를 추가하여 코드를 최적화 할 수 있다.

 

function bubbleSort(arr) {
    let noSwaps;
    for (let i = arr.length; i > 0; i--) {
        noSwaps = true;
        for (let j = 0; j < i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp
                noSwaps = false;
            }
        }
        if (noSwaps) break;
    }
    return arr;
}

참조

Udemy - Js 알고리즘 & 자료구조 강의