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

버블정렬(Bubble Sort) 이란?

• 매번 연속된 두개의 인덱스를 비교하여 정한 기준의 값을 뒤로 넘겨 정렬하는 알고리즘입니다.

• 오름차순으로 정렬하고자 할 경우, 비교시마다 큰 값이 뒤로 해당 값이 뒤로 이동하여 한바퀴 돌 고 난 후 가장 큰 값이 가장 마지막 위치에 있게 됩니다.

버블정렬(Bubble Sort) 동작 방식

1. 첫 번째 인덱스부터 시작하며 첫 번째 인덱스와 두 번째 인덱스의 값을 비교하여 첫 번째 인덱스가 더 크다면 위치를 변경합니다.
2. 두 번째 인덱스와 세 번째 인덱스의 값을 비교하여 두 번째 인덱스가 더 크다면 위치를 변경합니다.
3. 세 번째 인덱스와 네 번째 인덱스의 값을 비교하여 세 번째 인덱스가 더 크다면 위치를 변경합니다.
   .
   .
   .
   n-1. n-1 번째 인덱스와 n 번째 인덱스의 값을 비교하여 n-1 번째 인덱스가 더 크다면 위치를 변경합니다.

첫 번째 인덱스부터 n-1 번째 인덱스까지를 비교 인덱스로 하여 정렬을 하였습니다.
여기 까지가 1바퀴를 돌았다고 하며 이 때 가장 마지막 인덱스에는 가장 큰 값이 저장되어 있습니다.

위의 동작 방식처럼 첫 번째 인덱스 ~ n-2 번째 인덱스, 첫 번째 인덱스 ~ n-3 번째 인덱스 ... 첫 번째 인덱스 ~ 2 번째 인덱스까지 반복합니다.

ex) int[] arr = new int[]{1, 5, 30, 9, 7}을 버블 정렬방식을 적용합니다.

1. 첫 번째 인덱스 값 1과 두 번째 인덱스 값 5를 비교하여 더 큰 값을 두 번째 인덱스에 저장합니다.
   1 < 5 이므로 첫 번째 인덱스와 두 번째 인덱스는 변경하지 않습니다.

-> {1, 5, 30, 9, 7}

2. 두 번째 인덱스 값 5와 세 번째 인덱스 값 30을 비교하여 더 큰 값을 세 번째 인덱스에 저장합니다.
   5 < 30 이므로 두 번째 인덱스와 세 번째 인덱스는 변경하지 않습니다.

-> {1, 5, 30, 9, 7}

3. 세 번째 인덱스 값 30과 네 번째 인덱스 값 9를 비교하여 더 큰 값을 네 번째 인덱스에 저장합니다.
   30 > 9 이므로 세 번째 인덱스와 네 번째 인덱스는 변경됩니다.

-> {1, 5, 9, 30, 7}

4. 네 번째 인덱스 값 30과 다섯 번째 인덱스 값 7을 비교하여 더 큰 값을 다섯 번째 인덱스에 저장합니다.
   30 > 7 이므로 네 번째 인덱스와 다섯 번째 인덱스는 변경됩니다.

-> {1, 5, 9, 7, 30}
-> 여기까지가 한바퀴를 돌았다고 합니다.

5. 첫 번째 인덱스 값 1과 두 번째 인덱스 값 5를 비교하여 더 큰 값을 두 번째 인덱스에 저장합니다.
   1 < 5 이므로 첫 번째 인덱스와 두 번째 인덱스는 변경하지 않습니다.

-> {1, 5, 9, 7, 30}

6. 두 번째 인덱스 값 5와 세 번째 인덱스 값 9를 비교하여 더 큰 값을 세 번째 인덱스에 저장합니다.
   5 < 9 이므로 두 번째 인덱스와 세 번째 인덱스는 변경하지 않습니다.

-> {1, 5, 9, 7, 30}

7. 세 번째 인덱스 값 9와 네 번째 인덱스 값 7을 비교하여 더 큰 값을 네 번째 인덱스에 저장합니다.
   9 > 7 이므로 세 번째 인덱스와 네 번째 인덱스는 변경됩니다.

-> {1, 5, 7, 9, 30}

8. 다섯 번째 인덱스에는 가장 큰 값이 들어 있으므로 네 번째 인덱스 값과 다섯 번째 인덱스 값을 비교하지 않습니다.
   .
   .
   .

Java 버블 정렬 코드

    @Test
    public void sortTest(){
        int[] arr = new int[]{1, 10, 9, 5, 8, 3, 7};

        System.out.println("===== 정렬 이전 =====");
        for (int a : arr){
            System.out.print(a + " ");
        }
        System.out.println();

        bubbleSort(arr);

        System.out.println("===== 정렬 이후 =====");
        for (int a : arr){
            System.out.print(a + " ");
        }
    }

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

결과

===== 정렬 이전 =====
1 10 9 5 8 3 7 
===== 정렬 이후 =====
1 3 5 7 8 9 10 

시간 복잡도

첫 번째 인덱스부터 시작하여, n-1개, n-2개, ... , 1개의 비교를 반복하므로 시간 복잡도는 O(n^2) 입니다.