[정렬 알고리즘]Sorting Algorithm-BubbleSort

정렬 알고리즘(Sorting Algorithm)은 무엇일까?

정렬 알고리즘은 컬랙션(배열과 같은)의 아이템들을 어떤 종류의 순서로 재배열하는 과정이다. 

목록이나 트리 같은 데이터 구조의 정렬 등 다양하지만 배열에 초점을 두고 살펴보자.

 

여기서 핵심은 뭘 어떻게 비교해서 정렬하는지는 중요하지 않다. 오름차순이든, 내림차순이든, 순자를 기준으로 하든 상관없다. 

👉정렬 알고리즘 애니메이션

 

정렬 알고리즘을 배워야 하는 이유는?

• 정렬은 흔히 발생하기에 이것들이 어떻게 동작하는지 이해하는 것은 중요하다.
• 데이터들을 정렬하는 방법은 많고 각 알고리즘에는 장단점이 있기에 상황에 맞는 알고리즘을 사용해야한다.
• 정렬은 다양한 접근법을 제공하고 비판적 사고가 필요한 아주 좋은 도전과제이자 문제이다.

1. 버블 정렬(BubbleSort)

Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다.

정렬 과정

1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.
2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬해야하는 항목의 수가 감소한다.

Swaping

많은 정렬 알고리즘은 어떤 종류의 스와핑 기능을 포함한다. 데이터와 데이터를 비교하여 교환하는 즉, 바꾸는 방식을 말한다.

// ES5
function swap(arr, idx1, idx2) {
  let temp = arr[idx1];
  arr[idx1] = arr[idx2];
  arr[idx2] = temp;
}

// ES2015
const swap = (arr, idx1, idx2) => {
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}

 

구현하기

function bubbleSort(arr) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  }
    for (let i = arr.length; i > 0; i--) {
        for (let j = 0; j < i - 1; j++) {
            console.log(arr, arr[j], arr[j+1])
            if(arr[j] > arr[j+1]) {
                swap(arr, j, j+1)
            }
        }
        console.log('1 회전 완료!!')
    }
    return arr;
}
bubbleSort([37,45,29,8]);

처음 37과 45를 비교하고 그 다음 45와 29를 비교하여 swap한다. 45와 8을 비교하여 swap이 발생한다.

1회전씩 완료될 수록 비교하는 데이터가 줄어드는 것을 알 수 있다.

 

버블 정렬 최적화

function bubbleSort(arr) {
  let noSwaps;
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  }
    for (let i = arr.length; i > 0; i--) {
        noSwaps = true;
        for (let j = 0; j < i - 1; j++) {
            if(arr[j] > arr[j+1]) {
                swap(arr, j, j+1)
                noSwaps = false;
            }
        }
        if(noSwaps) break;
    }
    return arr;
}
bubbleSort([8,1,2,3,4,5,6,7]);

정렬이 거의 완료된 정렬일 경우 모두 완료한 뒤에도 계속 비교하는 루프를 가지고 있다. 

위 코드에서 noSwaps라는 상태를 이용해 루프를 중간에 차단하여 정렬이 완료되었다면 더이상의 비교를 멈추게 해주었다.

 

버블 정렬의 시간 복잡도

시간복잡도를 계산하면, (n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2이므로, 최악 그리고 평균적으로 O(n^2) 이다. 

그러나 데이터가 거의 정렬됐거나 이미 정렬이 끝난 상태에서 noSwaps 변수가 있는 신규 버전을 사용할 때는 (가능한 최선의 경우) O(n)에 가깝다.