거품 정렬(Bubble Sort)

Github : https://github.com/cocodori/study/tree/main/java-algorithm/algorithm01/sort-algorithm/src/main/java/sorting

정렬 알고리즘(Sorting algorithm)

컴퓨터 과학에서 정렬 알고리즘이란 원소를 어떤 기준으로 정렬하는 것을 말한다. 기준은 알파벳, 날짜, 숫자 등 무엇이든 될 수 있다. 탐색이나 병합 알고리즘 같은 경우 정렬된 리스트여야만 바르게 동작한다. 정렬 알고리즘은 다른 알고리즘의 전제 조건이 되므로 반드시 알아두어야 한다.

거품 정렬(Bubble Sort)

거품 정렬은 가까운 두 원소를 비교하여 정렬하는 알고리즘이다. 원소가 자리를 찾아가며 이동하는 모습이 거품이 수면으로 올라오는 듯한 모습을 보여서 지어진 이름이다. 시간 복잡도는

으로 상당히 느리지만 쉽게 구현할 수 있기 때문에 자주 언급된다.

거품 정렬을 구현하기 앞서 거품 정렬이 동작하는 방식에 대해 알아야 할 것 같다. 이런 원소 리스트가 있다고 하자. 오름차순으로 정렬한다고 가정한다. 

{8,3,5,7,4,1,2}

거품 정렬은 가까운 두 원소를 비교한다고 했다. 가까운. 어떤 기준도 없는 상태에서는 가까운지, 먼 지를 판단하기 어렵다. 그래서 거품 정렬은 두 번째 원소를 맨 처음 기준으로 한다. 두 번째 원소는 3이다. 이제 이 원소를 '가까운' 원소와 비교해야 한다. 거품 정렬에서 가깝다는 것은 이전 원소를 말한다. 맨 처음 기준이 되는 두 번째 원소 3 과 가까운 원소는 8이 된다. 이제 기준과 가까운 원소를 비교해서 가까운 원소가 기준보다 클 경우 자리를 바꾸면 된다.

기준 원소 < 가까운 원소

이 비교 연산을 원소에 대입하면 3 < 8이므로 자리 바꿈이 일어난다. 그 다음은 이제 뭘 비교해야 할까? 이 점이 헷갈릴수도 있다. 기준 원소는 3이 첫 번째 원소가 되면서 이전 원소가 사라졌기 때문이다. 이 부분을 헷갈리기 쉽다. 기준 원소에서 주의할 점은 원소의 값이 아니라 자리다. 맨 처음 기준으로 정했던 두 번째 원소의 다음 원소인 세 번째 원소가 그 다음 연산의 기준이다. 기준 원소는 자리 바꿈과 상관없이 한 칸씩 다음으로 밀린다. 두 번째 원소, 세 번째 원소, 네 번째 원소... 마지막 원소.

이제 두 번째 비교를 해보자. 기준 원소는 원래 기준이었던 원소의 다음 원소라고 했다. 그럼 이제 세 번째 원소 5가 기준이다. 세 번째 원소와 가장 가까운 원소는 이전 원소인 8이다. 5 < 8는 참이므로 자리 바꿈이 일어난다.

세 번째 비교까지 해보자. 세 번째 비교 연산의 기준이 될 원소는? 네 번째 원소 7이다. 네 번째 원소와 가까운 원소는 세 번째 원소이므로 7 < 8을 연산하게 된다. 역시 참이므로 자리 바꿈이 일어난다. 이렇게 한 싸이클 비교했을 때 원소 리스트에서 가장 큰 수가 마지막 자리에 위치한다.

[3, 5, 7, 4, 1, 2, 8]

제일 큰 수를 제일 뒤로 밀고, 그 다음 큰 수를 뒤로 밀고, 그 다음 큰 수를 뒤로 밀고, 그 다음 큰수를 뒤로 밀고. 이 작업을 반복할수록 작은 수는 앞으로 밀리고 밀리며 가장 작은 수부터 차례대로 정렬된 리스트의 모습을 띄게 된다.

주어진 원소 리스트 : {8,3,5,7,4,1,2}

cycle 1 [3, 5, 7, 4, 1, 2, 8]
cycle 2 [3, 5, 4, 1, 2, 7, 8]
cycle 3 [3, 4, 1, 2, 5, 7, 8]
cycle 4 [3, 1, 2, 4, 5, 7, 8]
cycle 5 [1, 2, 3, 4, 5, 7, 8]
cycle 6 [1, 2, 3, 4, 5, 7, 8]
cycle 7 [1, 2, 3, 4, 5, 7, 8]

1번 싸이클을 보자. 가장 큰 수였던 8이 가장 마지막 원소가 되었다.

2번 싸이클은 두 번째로 큰 수였던 7이 마지막 이전 원소(마지막-1)가 되었다.

3번 싸이클은 세 번째로 큰 수였던 5가 마지막 이전 원소의 이전 원소(마지막-2)가 되었다.

4번 싸이클은 4가 마지막-3

5번 싸이클은 3이 마지막 -4

여기서 알 수 있는 것

1. 가장 큰 수가 첫 번째 싸이클에 맨 뒷자리를 차지하니 더 이상 맨 뒷자리와 비교할 필요가 없다.
2. 이건 다음 싸이클도 마찬가지다.

cycle 1 [3, 5, 7, 4, 1, 2, 8]
cycle 2 [3, 5, 4, 1, 2, 7]
cycle 3 [3, 4, 1, 2, 5]
cycle 4 [3, 1, 2, 4]
cycle 5 [1, 2, 3]
cycle 6 [1, 2]
cycle 7 [1]

그럼 이렇게만 비교해도 괜찮다는 뜻이다. 첫 번째 싸이클을 제외한 나머지 싸이클은 마지막 원소와는 비교할 필요가 없다. 첫 번째 싸이클에서 이미 비교를 마치고 현재 원소 리스트에서 가장 크다고 결정한 원소이기 때문이다. 그러니 다시 한 번 비교하는 것은 낭비다. 따라서 원소의 크기 - (n번째 싸이클-1)만큼만 비교하면 된다.

위에서 설명한 모든 것을

1. 두 번째 원소가 첫 번째 기준 원소다.
2. 기준 원소에서 중요한 것은 값이 아니라 자리, 즉 위치다.
3. '가까운' 원소는 기준이 되는 원소 '이전'에 위치하는 원소를 말한다.
4. 비교가 끝날 때마다 기준 원소는 그 다음 위치로 한 칸씩 이동한다.
5. 첫 번째 싸이클을 제외한 나머지 싸이클은 원소의 크기-(n번째 싸이클-1) 비교하면 된다.

내가 그린 버블 소트

각 싸이클 안에서 비교하는 원소를 비교해 차례로 자리를 바꾸는 과정을 직접 써보았다. 첫 번째 싸이클은 전체를 다 순회하며 비교하지만, 다음 싸이클로 넘어갈수록 비교하는 횟수가 줄어드는 것을 볼 수 있다. 7번의 싸이클을 반복해야 하지만 위 그림에서 보면 5번째 싸이클까지 마치면 이미 정렬이 끝난 상태다. 여기서 싸이클을 더 도는 것은 낭비다. 실제로는 6번째 싸이클까지 돌아야 한다. 6번째 싸이클에서 자리를 바꾼 원소가 하나도 없다면 이미 정렬이 끝난다는 것이므로 비교를 멈춰줄 수 있다.

거품 정렬 구현

코드는 간단하다.

public class Bubble {
    public static void main(String[] args) {
        bubbleSort(new int[]{8,3,5,7,4,1,2});
    }

    public static void bubbleSort(int[] arr) {
         int temp = 0;

         for (int i = 0; i < arr.length; i++) {
             for (int j = 1; j < arr.length-i; j++) {
                 if (arr[j] < arr[j-1]) {
                     temp = arr[j-1];
                     arr[j-1] = arr[j];
                     arr[j] = temp;
                 }
             }
             System.out.println(Arrays.toString(arr));
         } // end - for
    }
}

첫 번째 반복문이 위에서 얘기했던 싸이클이다. 각 싸이클 내에서 원소 리스트를 순회하는 반복문이 하나 더 들어있다. 그리고 그 안에 기준 원소와 이전 원소를 비교하여 true일 때 자리 바꿈하는 코드가 들어있다. 이대로도 충분하지만 나름대로 읽기 좋게 메소드를 분기해봤다.

private static void bubbleSort(int[] arr) {
    int temp = 0;

    for (int i = 0; i < arr.length; i++) {
        for (int j = 1; j < arr.length-i; j++) {
            if (isPreviousElementBigger(arr[j], arr[j-1])) {
                arr = swapElements(arr, j);
            }
        }
        System.out.println(Arrays.toString(arr));
    } // end - for
}

//이전 요소가 더 크다면 true를 반환한다.
private static boolean isPreviousElementBigger(int element, int prevElement) {
    return element < prevElement;
}

//비교하여 자리를 바꾼 다음 결과를 반환한다.
private static int[] swapElements(int[] arr, int j) {
    int temp;

    temp = arr[j];
    arr[j] = arr[j -1];
    arr[j -1] = temp;

    return arr;
}

if (arr[j] < arr[j-1])의 경우 무슨 비교를 하는 건지 코드만 봐서는 알 수 없다. 그래서 정확하게 이전 원소와 비교한다고 명시하기 위해 isPreviousElementBigger()이란 이름의 메소드로 분기했다. 원소의 자리를 바꾸는 코드도 swapElements()란 이름으로 원소의 위치를 변경하는 작업을 한다는 것을 이름으로 명시했다.

Github : https://github.com/cocodori/study/tree/main/java-algorithm/algorithm01/sort-algorithm/src/main/java/sorting