07 버블 정렬

  지금 부터는 정렬에 대해서 공부하려고 한다. 정렬이란 말 그대로 데이터를 일정한 기준을 가지고 재배열하는 과정을 말한다. 정렬을 하는 방식에는 많은 방법이 존재하고 각각의 정렬 알고리즘마다 장/단점을 지니고 있다. 또한 정렬을 할 수 있는 많은 메서드들이 존재한다. 그러한 메서드들을 잘 활용하는것도 중요하겠지만, 그 동작 원리를 아는것 또한 굉장히 중요한 일이다. 

 

대표적이고 일반적인 정렬 방식이 버블 정렬, 선택 정렬, 삽입 정렬이 있고 그 뒤로 효율성을 개선시킨 정렬 방식들이 있다. 버블 정렬, 선택 정렬, 삽입 정렬은 효율성이 떨어져 잘 사용되지는 않지만 특정 상황에서는 유용한 정렬방식일 수 있다.

 

7.1 버블 정렬 : 개요

  버블 정렬은 흔히 사용되지는 않는다. 다른 정렬 알고리즘에 비해 비효율적이기 때문이다. 하지만 다른 정렬 알고리즘과 비교하기 위해서는 알아 둘 필요가 있다. 버블 정렬의 작동 방식은 루프를 돌면서 각 요소를 해당 요소와 그 다음 요소와 비교하여 스왑하는 것이다. 예를 들어 오름차순으로 정렬한다면, 해당 요소가 다음 요소보다 값이 크다면 해당 요소와 다음 요소를 교환해 주는 것이다. 

 

  결국 루프의 한 바퀴가 돌때마다 가장 큰 요소가 가장 오른쪽에 정렬되게 될 것이다. 여기서 중요한 점은 루프가 한 바퀴 돌때마다 가장 큰 요소가 가장 오른쪽에 정렬되기 때문에 그 다음 루프가 돌아갈때는 가장 오른쪽에 있는 요소는 제외하고 나머지를 비교해야 한다. 즉, 반복을 거듭할때마다 정렬해야 하는 요소수는 줄어든다는 것이다!!

 

  우선 버블 정렬을 구현하기 전에 요소를 스왑하는 방법부터 알아야 한다.

ES5(가독성이 좋음)
function swap(arr, idx1, idx2) {
  var temp = arr[idx1];
  arr[idx1] = arr[idx2]; // 배열 요소 갱신
  arr[idx2] = temp; // 배열 요소 갱신
}

ES6(가독성은 떨어지지만, 코드가 짧음)
const swap = (arr, idx1, idx2) => {
  [arr[idx1],arr[idx2]] = [arr[idx2],arr[idx1]];
}

 

  요소를 스왑하는 방법은 그렇게 어렵지가 않다. 말 그대로 하나의 요소를 미리 변수에 담아놓고 하나의 요소에 다른 요소를 할당해주고 나머지 요소에 변수에 미리 담아놓은 요소를 할당해 주면 된다. ES5와 ES6코드 둘 다 같은 의미이지만 표현이 조금 다르기 때문에 더 편리한 방법을 사용하면 될 것 같다.

 

의사코드(강사님이 만들어주심)

1. 함수를 정의하여 배열을 인수로 받고 배열의 요소들은 숫자라고 가정한다.

2. i라는 변수를 만들고 배열의 맨 끝에서 루프를 시작하여 맨 앞에서 끝낸다.

3. 루프 안에는 중첩 루프가 있고 j를 변수로 만들고, 내부 루프는 처음부터 i-1까지 반복된다.

4. arr[j]가 arr[j+1]보다 크다면 두 값을 스왑한다.

5. 그리고 arr을 반환한다.

 

7.2 버블 정렬 : 구현

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를 끝에서부터 시작해서 반복을 하는 이유는 가장 루프가 한 바퀴 돌때마다 가장 오른쪽에는 가장 큰 요소 값이 정렬이 되어 있기 때문에 더 이상 비교 할 필요가 없기 때문에 해당 요소를 제외하고 비교하기 위해 i를 끝에서 부터 반복시키는 것이다. 

 

7.2 버블 정렬 : 최적화

  버블 정렬을 했을때 위의 코드의 문제점은 만약 배열이 정렬이 대부분 이뤄져 있고 일부분만 정렬이 되어 있지 않다고 생각해보자. 그런 경우에도 스왑이 일어나지 않을뿐 반복은 계속해서 일어날것이다. 이는 비효율적이는 이를 해결하기 루프가 되는 와중에 단 한 번이라도 스왑이 일어나지 않았다면 반복을 그만두는 조건을 달면 되는 것이다. 반복이 단 한 번도 일어나지 않았다는 것은 반대로 말하면 더 이상 스왑할 요소가 없는것이고 정렬이 완료되어 있다는 것이기 때문이다.

function bubbleSort(arr){
    let noSwap;

    for(var i = arr.length; i > 0; i--){
        noSwap = true; // 최적화를 위해 비교해야 할 요소의 개수를 하나씩 줄여나감
        for(var j = 0; j < i - 1; j++){ // 앞에서 부터 해당요소와 그 다음 요소를 비교해서 스왑
            if(arr[j] > arr[j+1]){
                var temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                noSwap = false;         
            }
        }
        if(noSwap) break; // 즉 한바퀴 쭉 돌았는데, 교환이 일어나지 않으면 그대로 true일 것이고, 그럼 더 이상
        //바꿀게 없는 거니까 전체 반복을 종료함!!!
    }
    return arr;
}

  참고로, 스왑문을 ES6의 방식으로 구현해도 상관없다. 개인적으로 코드 줄 수도 크게 차이가 나지 않고, ES5에서의 스왑방식이 공부하는 입장에서 조금 더 직관적이라 ES5방식을 이용하여 스왑하는 코드를 작성하였다.