Bubble Sort(버블정렬)

1. 버블 정렬이란?

거품정렬 또는 버블정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)으로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 양방향으로 번갈아 수행하면 칵테일 정렬이 된다.

출처 : https://ko.wikipedia.org/wiki/거품_정렬

거품 정렬 - 위키백과, 우리 모두의 백과사전

 

2. 버블 정렬 시간복잡도 / 공간 복잡도

평균	최악	메모리	안정성
O(N^2)	O(N^2)	O(1)	TRUE

그런데 평균과 최악이 왜 N^2이 나오는지 궁금하였다. 시간복잡도와 공간복잡도가 이렇게 나온다는 것만 알았지 어떻게 이런 식이 도출되었는지는 몰라서 이번 기회에 공부해 보기로 하였다. 

일단 평균은 정렬하는데 소요되는 평균적인 시간을 나타낸다. 그리고 최악은 제일 안좋은 경우를 정렬 하였을 경우를 말한다. 여기서 제일 안좋은 경우는 예를 들면 5,4,3,2,1 이런 식으로 정렬되어있는 경우이다. 왜냐하면 처음부터 끝까지 모두다 정렬을 수행해야하기 때문이다.

평균과 최악을 구하기 앞서서 버블정렬은 어떻게 수행이 되는지 알아보자!

[버블정렬 수행 과정]

1. 비교할 숫자1와 그 다음 숫자2를 비교한다. 
   
   • 비교할 숫자1 > 다음 숫자2일 때 
     • 비교할 숫자1과 그 다음 숫자2 위치를 서로 바꾼다. 
   • 비교할 숫자1 <= 다음 숫자2일 때
     • 그대로 둔다.
2. 1번의 과정을 N-1번 수행한다.

글로 썼을 때는 어떤 말인지 와닿지가 않을 수가 있다. 하지만 그림으로 본다면 아마도(?) 누구나 이해할 수 있을 것이다. 만약 이해가 안되었을 경우에는 제가 설명이 불충분해서 그런거지 절대 자기 탓은 아니다. (피드백 주시면 더 쉽게 설명해보겠습니다.) 

[수행과정 그림 설명]

5 4 3 2 1

버블정렬 1회차 수행과정

 

첫 1회 수행은 이렇게 마쳤다. 2회 수행은 [4, 3, 2, 1, 5] 에서 맨 앞에 요소인 4부터 시작한다. 다음 그림을 보면 이해가 쉽게 갈 것이다. 

버블정렬 2회차 설명

맨 밑에 결론을 보자면 4부터 시작해서 5이전 위치에 4가 들어왔다. 정렬을 하다보니 버블정렬을 제일 큰 수가 맨 오른쪽에 위치하고 그 다음 큰 숫자가 왼쪽에 차곡차곡 이동하는 것을 알수 있다. 이런 식으로 정렬을 하다보면 맨 마지막 수행할 경우 [1, 2, 3, 4, 5]의 결과가 나온다. 

[프로그래밍 코드]
프로그래밍 코드를 보자면 아래와 같다. 버블 소트 안에 sort method부분이 정렬 핵심 로직이다. 

class BubbleSort {
    private int[] arr;

    BubbleSort(int[] arr) {
        this.arr = arr;
    }

    public void sort() {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    }

    public void display() {
        for (int number : arr) {
            System.out.print(number + " ");
        }
        System.out.println();
    }

}

아래는 처음부터 버블정렬의 과정을 프로그램으로 출력을 하였다. 

--1회차--
5 4 3 2 1 
4 5 3 2 1 
4 3 5 2 1 
4 3 2 5 1 
4 3 2 1 5

--2회차--
3 4 2 1 5 
3 2 4 1 5 
3 2 1 4 5 

--3회차--
2 3 1 4 5 
2 1 3 4 5 

--4회차--
1 2 3 4 5

정렬이 4회차로 한 것은 N-1번 수행하기 때문이다. 이것은 가장 큰수가 맨 오른쪽으로 위치하고, 계속 그 다음 큰 수가 맨 오른쪽으로 위치하기 때문이다.