[JAVA] 정렬 알고리즘 버블 정렬(Bubble Sort)

알고리즘을 처음 시작하는 단계라면 가장 자주 접할 수 있는 문제 중 하나가 "정렬(Sort)" 일 것입니다.

왜 정렬이 자주 나오고 질문되는 것일까요 ?

 

그 이유는 정렬을 하는 방법이 매우 다양하고, 이를 비교하여 알고리즘의 효율성 차이를 잘 나타내 줄 수 있기 때문입니다.

빈번하게 나오는 몇몇 정렬 알고리즘에 대한 비교를 순차적으로 포스팅 하도록 하겠습니다.

그럼 가장 첫번째로 알아볼 버블 정렬(Bubble Sort)의 기본 개념부터 다루도록 하죠

 

버블 정렬(Bubble Sort)

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

*위키백과 참조

위키백과의 설명에 따르면 버블 정렬(Bubble Sort)이 자주 사용된다고 하지만, 개인적으로 거의 사용되는 일이 없다고 생각합니다. 

그 이유 중 하나는 다른 몇 가지 정렬과 비교해도 상당히 비효율적인 측면이 있기 때문입니다.

또한 일부 학자들은 더 이상 버블 정렬(Bubble Sort)을 가르칠 필요가 없다고 말할 만큼 필요 없는 알고리즘 중 하나로 분류되고 있습니다.

 

하지만 버블 정렬(Bubble Sort)을 알아보는 이유는 무엇일까요 ?

직관적이고, 구현이 쉽기 때문에 정렬을 처음 공부할 때 가볍게 접근하기 좋다는 것입니다.

 

정렬을 이해할 때는 그림을 통해 이해하는 것이 쉽기 때문에, 아래 그림과 함께 버블 정렬(Bubble Sort)의 기본 원리를 파악해보도록 하겠습니다.

 

정렬이 안된 초기상태의 배열이 있습니다.

가장 먼저 인접한 두 원소인 5와 3을 비교합니다.

5와 3 중 더 큰 수를 오른쪽으로 교환하여 줍니다.

다음 인접한 두 수인 5와 8을 비교하여 줍니다.

5와 8 중 큰 수를 오른쪽으로 보내야 하지만 이미 8이 큰 수 이므로 교환하지 않습니다.

다음 8과 1을 비교하여 줍니다.

마찬가지로 두 수 중 더 큰 수를 오른쪽으로 교환해 줍니다.

다음 8과 2를 비교하고 더 큰 수인 8과 교환이 일어납니다.

마지막으로 8과 7을 비교하고 더 큰 수인 8과 교환이 일어납니다.

결과적으로 가장 큰 수인 8은 리스트의 가장 끝쪽에 정렬이 됩니다.

한 번의 반복을 통해 가장 큰 레코드가 리스트의 오른쪽 끝에 이동이 되었고, 8을 제외한 나머지를 다시 반복합니다.

 

---

다음과 같이 오른쪽 레코드의 정렬이 끝나면 n-1번째 부터 정렬을 시작한다.

즉, 시간복잡도로 계산해본다면

첫번째, n 개의 원소 비교

두번째, n-1개의 원소 비교

세번째, n-2개의 원소 비교

...

n,n-1,n-2,...2,1번 = n(n-1)/2

이는 최악의 경우(Worst Case)인 입력 자료가 역순인 경우 한 번 교환하기 위해 3번의 이동(Swap)이 필요하므로 (비교횟수 *3)번 = 3n(n-1)/2 이므로

시간복잡도를 빅오로 표현해 본다면, 평균적으로 O(N²) 이 나오게 됩니다.

 

최상의 경우(Best Case)는 입력자료가 이미 정렬이 된 상태라면 자료의 이동이 발생하지 않으므로 O(N) 입니다.

 

 

 

이미지 참조 https://astinlen.tistory.com/archive/200709

---

 

버블 정렬(Bubble Sort) 구현

 
public class BubbleSort {
 
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                }
            }
        }
    }
 
    public static void swap(int[] array, int source, int target) {
        int temp = array[source];
        array[source] = array[target];
        array[target] = temp;
 
    }
 
    public static void printArray(int[] array) {
        for (int data : array) {
            System.out.print(data + " ");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        int[] item = new int[] { 5, 3, 8, 1, 2, 7 };
        System.out.println("정렬 전");
        printArray(item);
        bubbleSort(item);
        System.out.println("정렬 후");
        printArray(item);
 
    }
 
}
 

 

결과값

버블 정렬(Bubble Sort) 의 구현은 다음과 같습니다.

구현이 쉽다고 하는 이유는 다중(여기서는 2중)For문의 이해만으로 구현할 수 있기 때문이라고 생각합니다.

코드의 설명을 돕자면 다음과 같습니다.

bubbleSort 를 구현하기 위한 메소드는 배열을 인자값으로 받습니다. (4번째줄)

첫번째 For문(외부)은 배열의 길이(n)만큼 반복문을 돌려야 합니다. (5번째줄)

첫번째 정렬이 끝나면 가장 끝에 원소는 정렬이 된 상태이므로 두번째부터(내부For문)는 끝을 제외한 나머지 길이만큼(n-1) 반복문을 돌립니다. (6번째)

이 때 인접한 두 원소를 비교해야 합니다. (7번째줄)

비교하여 인접한 원소를 오른쪽으로 교환합니다. (8번째줄)

이때 저는 Swap문을 따로 메소드로 빼서 구현하였습니다. ( 이유는 추후 Swap을 자주 쓰게 될텐데 이 때의 가독성을 높히기 위해서 )

swap은 stack 등에서도 자주 나옵니다.

데이터의 교환이 일어나기 위해서는 빈공간의 변수가 한개 더 필요하기 때문에 temp 라는 빈 공간의 변수를 선언했고, 이를 통해 변수 안에 데이터를 교환하여 저장하였습니다.

printArray는 데이터를 보여주기 위해 메소드로 만들었습니다. (향상된 For문)

이해가 가지 않으신다면 [더보기] 를 통해 조금 더 명시적으로 확인이 가능합니다.

 
public class BubbleSort {
 
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print("버블정렬" + (i+1) + "회차 \n");
            for(int data : array) {
                System.out.print(data + " ");
            }
            for (int j = 0; j < array.length - i - 1; j++) {
                System.out.print("\n");
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                }
                for(int data : array) {
                    System.out.print(data + " ");
                }
            }
            System.out.println("\n");
 
        }
        System.out.print("버블 정렬(Bubble Sort) 완료");
 
    }
 
    public static void swap(int[] array, int source, int target) {
        int temp = array[source];
        array[source] = array[target];
        array[target] = temp;
 
    }
 
    public static void main(String[] args) {
        int[] item = new int[] { 5,3,8,1,2,7 };
        bubbleSort(item);
 
    }
 
}
 

---

버블 정렬(Bubble Sort) 정리

최악의 시간복잡도도 O(N²) 을 갖는다.
인접한 값만 비교하면 되는 방식이기 때문에 직관적이고, 구현이 매우 쉽다.
효율적인 알고리즘에서는 사용되지 않는다.
추가적인 배열을 만들 필요가 없는 메모리 측면에서 제자리 정렬 알고리즘 (in-place algorithm) 이라고 한다.
버블 정렬은 안정적(Stable) 정렬이다.

---

다른 정렬들과의 시간복잡도 비교

정렬 알고리즘은 시간복잡도를 비교하여 알아두는 것이 좋다.

 

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html 참조

---

이번 포스팅에서는 정렬의 시작인 버블 정렬(Bubble Sort)에 대해 포스팅 해보았습니다.

버블 정렬부터 포스팅을 시작한 이유는 아주 단순합니다.

구현이 쉽지만, 비효율적인 측면을 시작으로 점차 효율적인 알고리즘을 포스팅하기 위함입니다.

 

또한 기존 버블정렬을 개선한 향상된 버블정렬에 대해서는 다루지 않았습니다. ( 시간복잡도는 같다 )

기본적인 부분만 포스팅해두고 싶었기 때문인데요.

향상된 버블정렬의 포인트는 자료의 교환이 더이상 발생하지 않으면 다음 단계를 생략하는 방법입니다.

 

향상된 버블정렬에 대해 추후 포스팅할 기회가 있다면 하도록 하겠습니다. (정리할게 많아서..)

그럼 2만