버블 정렬(Bubble Sort) 알고리즘이란 무엇인가? Kotlin으로 버블 정렬 직접 구현하면서 알아보기

Bubble Sort 알고리즘이란 무엇인가?

Bubble Sort 알고리즘은 인접한 두 개의 원소를 반복적으로 비교해 순서를 바꾸는 방식으로 정렬하는 알고리즘이다. 배열이 있다고 했을 때 배열의 처음부터 끝까지 이를 한 번 반복하면 배열의 맨 마지막에는 가장 큰 원소가 남게 된다. 이후 한 번 더 반복하면 배열의 맨 마지막에는 배열에서 가장 큰 원소가, 배열의 맨 마지막에서 두 번째 자리에는 배열에서 두번째로 큰 원소가 위치하게 된다. 이를 원소의 개수만큼 반복하면 전체 원소가 순서대로 배치된다.

 

이 것이 Bubble Sort 알고리즘이라고 불리게 된 이유는 큰 원소가 점점 맨 뒤로 이동하는 것이 마치 Bubble(거품) 같아서 라고 한다. 아마 글로는 잘 이해가 가지 않을 것이다. 아래에서 그림으로 보면서 알고리즘을 이해해보도록 하자.

 

그림으로 보는 Bubble Sort 알고리즘

1. 아래와 같이 5, 4, 6, 2, 1 순서의 배열이 있다고 해보자

 

2. 처음 두개의 원소를 비교하면 5가 4보다 더 크므로 바뀌어야 한다.

  

3. 그 다음은 5와 6이 비교된다. 이때 6은 5보다 크므로 바뀌지 않는다.

 

4. 이후 6과 2를 비교한다. 6은 2보다 크므로 둘의 자리를 바꾼다.

 

5. 6과 1을 비교한다. 6은 1보다 크므로 자리를 바꾼다.

 

7. 이를 통해 한 번의 반복이 끝났고, 맨 뒤에는 가장 큰 원소인 6이 위치한 것을 확인할 수 있다.

 

8. 자 이제 다시 처음으로 돌아와, 4와 5를 비교한다. 4가 5보다 작으므로 자리를 바꿀 필요가 없다.

 

9. 이번엔 5와 2를 비교한다.  5는 2보다 크므로 자리를 바꾼다.

 

10. 이번에는 5와 1을 비교한다. 5는 1보다 크므로 자리를 바꾼다.

 

11. 자 이제 전체 배열에서 두 번째로 큰 5가 맨 뒤에서 두 번째에 위치하게 되었다.

 

12. 다시 처음으로 돌아와 4와 2를 비교한다. 4가 2보다 크므로 4를 뒤로 옮긴다.

 

13. 4와 1을 비교한다. 4가 1보다 크므로 4를 뒤로 옮긴다.

 

14. 자 이제 3번째로 큰 4가 뒤에서 3번째 자리에 왔다.

 

15. 다시 처음으로 와 2와 1을 비교한다. 2가 1보다 크므로 자리를 바꾼다.

16. 자 이제 모든 정렬이 완료되었다.

 

 

Bubble Sort 알고리즘 구현하기

Bubble sort 알고리즘을 구현하기 위해서는 먼저 각 원소들이 전체를 순환하면서 비교하는 알고리즘을 구현해야 한다. 이는 아래와 같이 구현할 수 있다. 0번 원소부터 max번 원소까지 다음 원소와의 비교 후 바꾸기 연산을 반복하면 된다.

for (pointer in 0..max) {
    if(array[pointer] > array[pointer+1]){
        var tmp = array[pointer]
        array[pointer] = array[pointer+1]
        array[pointer+1] = tmp
    }
}

 

이제 위에서 max의 값을 구해야한다. array에 5개의 원소가 존재할 때 4번, 3번, 2번, 1번의 비교가 필요하므로 max는 3, 2, 1, 0 이여야 한다.

*max가 3이어야 0, 1, 2, 3번 노드에 대한 비교가 들어가 4번 비교가 된다.

 

따라서 전체 코드는 아래와 같이 작성할 수 있다.

fun bubbleSort(array: IntArray) {
    for(max array.size-2 downTo 0) {
        for (pointer in 0..max) {
            if(array[pointer] > array[pointer+1]){
                var tmp = array[pointer]
                array[pointer] = array[pointer+1]
                array[pointer+1] = tmp
            }
        }
    }
}

 

이를 테스트 해보면 정상적으로 동작하는 것을 확인할 수 있다.

 

Bubble Sort  알고리즘의 복잡도

Bubble Sort 알고리즘의 시간 복잡도

Array의 Size가 N이라 할 때 Bubble Sort는 (N-1) + (N-2) + ... 1 번의 연산이 필요하므로 O(N^2)의 시간 복잡도를 가진다.

 

Bubble Sort 알고리즘의 공간 복잡도

Bubble Sort는 추가공간을 사용하지 않고 기존 공간에서 주어진 공간에서 정렬을 수행하므로, O(1)의 공간 복잡도를 가진다.

 

정리

Bubble Sort는 간단하면서 강력한 정렬 알고리즘이다. 시간 복잡도 측면에서는 좋지 않은 알고리즘이지만, 공간 복잡도 측면에서는 뛰어난 알고리즘이다. 기초적인 알고리즘이지만 중요한 알고리즘이니 제대로 알고 가자.

 

하지만 이후 배울 알고리즘들 중에서는 공간 복잡도가 O(1)이면서 시간 복잡도가 O(logN)인 정렬 알고리즘 또한 존재한다.