버블 정렬 (Bubble Sort) - 아이디어, 작동 원리, 성능 및 시간 복잡도, 특징, 자바 구현 코드

버블 정렬 

 

비교 기반 알고리즘 중 가장 기초가 되는 버블 정렬에 대해 살펴본다. 

 

아이디어 

 

오름차순 정렬이라고 할 때, 모든 인접한 두 값을 비교하여 왼쪽의 값이 더 큰 경우 자리를 하나씩 바꾸는 과정을 반복해서 정렬한다. 

 

버블 정렬은 왼쪽 -> 오른쪽, 오른쪽 -> 왼쪽 진행방향을 두 가지로 나눠서 생각해볼 수 있다.

하지만 결론은 동일하게 나타난다. 

 

 

작동 원리 

 

다음과 같은 데이터를 정렬하는 과정을 통해 실제 작동 원리를 살펴보자 .

 

int[] arr = {50 20 30 10 40};

 

50 20 30 10 40의 숫자 중에서 

첫 번째부터 마지막까지 각각을

왼쪽에서부터 오른쪽으로 하나씩 옮겨가면서 비교를 한다. 

 

예를 들어 다음과 같다. 

 

i=0)

 

1) 먼저 50과 20을 비교한다. 왼쪽의 값이 더 크므로 50과 20을 바꾼다. 

-> 20 50 30 10 40 

 

2) 이어서 50과 30을 비교한다. 왼쪽의 값이 더 크므로 30과 50을 바꾼다. 

-> 20 30 50 10 40 

 

3) 이어서 50과 10을 비교한다. 왼쪽의 값이 더 크므로 10과 50을 바꾼다. 

-> 20 30 10 50 40 

 

4) 이어서 50과 40을 비교한다. 왼쪽의 값이 더 크므로 50과 40을 바꾼다. 

-> 20 30 10 40 50 

 

 

 

이렇게 하여 50이 맨 마지막에 오게 되는 오름차순 정렬 pass1(패스)이 끝난다. 

이것을 코드에서 보면 2중 반복문의 첫번째 반복문인 것을 볼 수 있다. 

 

 

public static int[] bubbleSortAsc(int[] array){
    int[] arranged = Arrays.copyOf(array, array.length);

    for(int i =0; i< array.length-1; i++){
       for(int j =0; j < array.length -1 -i; j++){

          if (arranged[j] > arranged[j+1]){
             swap(arranged, j);
          }
       }
    }
    return arranged;
}

 

첫 번째 반복문, 즉 i가 돌아가는 과정이 하나의 패스이며, 따라서 n-1번의 패스를 반복한다. 

 

두 번째 반복문, 즉 j가 돌아가는 과정에서는 요소 하나하나의 비교 및 교환이 발생한다. 

j가 0부터 시작하므로 왼쪽에서 오른쪽으로 가는 진행이라 할 수 있다. 

 

 

전체 과정 

 

다음 데이터가 진행되는 전체 과정을 살펴보자.

int[] arr = {60, 20, 70, 10, 80, 30, 50, 40};

 

패스 1 (i=0) -> 20 60 10 70 30 50 40 80

패스 2 (i=1) -> 20 10 60 30 50 40 70 80

패스 3 (i=2) -> 10 20 30 50 40 60 70 80

패스 4 (i=3) -> 10 20 30 40 50 60 70 80

패스 5 (i=4) -> 10 20 30 40 50 60 70 80

패스 6 (i=5) -> 10 20 30 40 50 60 70 80

패스 7 (i=6) -> 10 20 30 40 50 60 70 80

 

 

인접한 두개의 값을 비교하여 왼쪽의 값이 큰 경우 자리 바꿈을 계속한다.

 

실제 데이터 흐름을 다음과 같이 살펴보자.

 

 

 

 

 

그런데 여기서 주목해볼 점은 패스 3에서 40과 50이 마지막으로 자리 바꿈이 일어나고 패스 4부터는 자리바꿈이 발생하지 않는 것을 볼 수 있다. 

 

즉, 이는 패스 5부터는 생략이 가능하다는 것을 알 수 있다. 

 

이를 고려하여 알고리즘을 개선할 수 있다. 즉 패스 진행에서 boolean을 통해 자리바꿈이 일어났는지 여부를 체크하고, 자리바꿈이 더 이상 발생하지 않는다면 그 시점이후로는 반복문을 종료하고 더 이상 실행하지 않는 것이다. 

 

public static int[] bubbleSortAsc(int[] array){
		 int[] arranged = Arrays.copyOf(array, array.length);
		 boolean exchange;

		 for(int i =0; i< array.length- 1; i++){
			 exchange = false;
			 for(int j =0; j < array.length -1 -i; j++){
				 if (arranged[j] > arranged[j+1]){
					 swap(arranged, j);
					 exchange = true;
				 }
			 }
			 if (!exchange){
				 break;
			 }

		 }
		 return arranged;
	}

 

위에서는 boolean 값 exchange를 변수로 추가하여 이를 통해 해당 패스 이상의 반복문 실행 여부를 체크하고, 만약 더 이상 자리 바꿈이 발생하지 않으면 false 값을 밑으로 내려 탐색을 종료시킨다. 

 

 

 

 

시간 복잡도 (성능) 

 

 

버블 정렬의 성능을 분석해보자.

 

첫 번째 반복문이 데이터 개수 n 만큼 돌고,  두번째 반복문이 n 만큼 돈다. 따라서 O(n^2)이다. 

 

다음과 같이 계산 할 수도 있다. 

 

 

바깥 루프 i	안쪽 루프 j에서의 비교 횟수
i = 0	n-1
i = 1	n-2
i = 2	n-3
...	...
i = (n-3)	2
i = (n-2)	1

 

따라서 연산 횟수를 모두 더하면 

(n-1) + (n-2) + (n-3) + ... + 1 = n(n-1)/2

=> n^2 

 

 

 

그런데 만약 boolean 값을 추가해 개선한 알고리즘으로 정렬을 수행할 때 숫자가 모두 정렬된 상태라면 어떨까? 

 

즉 처음 주어지는 배열이 {10, 20, 30, 40, 50}인 경우이다. 

 

이 경우 비교가 한 번도 발생하지 않으므로 pass1만 마치고 탐색이 종료된다. 즉, n-1번의 연산으로 종료된다. 

 

따라서 이 경우 시간 복잡도는 O(n)이다. 

 

반면 역순으로 정렬된다면 어떨까? 즉 입력 배열이 {50, 40, 30, 20, 10}인 경우다. 

 

이때는 10번 비교하며 위에서 구한 값인 O(n^2)이 적용된다. 

 

즉, 이처럼 입력 데이터의 상태에 따라 성능이 달라지는 것을 볼 수 있다. 

 

 

 

int[] arr0 = {10, 20, 30, 40, 50};
int[] sortedArr0_1 = bubbleSortAsc(arr0);
Assertions.assertArrayEquals(new int[]{10, 20, 30, 40, 50}, sortedArr0_1);

int[] arr1 = {50, 20, 30, 10, 40};
int[] sortedArr1_1 = bubbleSortAsc(arr1);
Assertions.assertArrayEquals(new int[]{10, 20, 30, 40, 50}, sortedArr1_1);

 

 

 

 

 

 

특징

 

1. 가장 직관적이고 쉬운 정렬 알고리즘 

 

2. 경우에 따른 성능 차이가 발생한다. 

- 제자리로 정렬되어 있는 경우 -> O(n)

- 평균/최악 -> O(n^2)

 

3. 안정적 정렬 알고리즘 O

 

4. 제자리 정렬 알고리즘 O

 

 

 

 

 

자바 구현 코드 

 

package basic.sort;

import java.util.Arrays;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class BubbleSort {
   public static void main(String[] args) {
      test();
   }

   @Test
   public static void test(){
      int[] arr0 = {10, 20, 30, 40, 50};
      int[] sortedArr0_1 = bubbleSortAsc(arr0);
      Assertions.assertArrayEquals(new int[]{10, 20, 30, 40, 50}, sortedArr0_1);

      int[] arr1 = {50, 20, 30, 10, 40};
      int[] sortedArr1_1 = bubbleSortAsc(arr1);
      Assertions.assertArrayEquals(new int[]{10, 20, 30, 40, 50}, sortedArr1_1);

      int[] arr2 = {4, 7, 2, 10, 180, 99, 50, 30, 15, 0};
      int[] sortedArr2_1 = bubbleSortAsc(arr2);
      int[] sortedArr2_2 = bubbleSortDesc(arr2);
      Assertions.assertArrayEquals(new int[]{0, 2, 4, 7, 10, 15, 30, 50, 99, 180}, sortedArr2_1);
      Assertions.assertArrayEquals(new int[]{180, 99, 50, 30, 15, 10, 7, 4, 2, 0}, sortedArr2_2);

      int[] arr3 = {1};
      int[] sortedArr3_1 = bubbleSortAsc(arr3);
      int[] sortedArr3_2 = bubbleSortDesc(arr3);
      Assertions.assertArrayEquals(new int[]{1}, sortedArr3_1);
      Assertions.assertArrayEquals(new int[]{1}, sortedArr3_2);

      int[] arr4 = {};
      int[] sortedArr4_1 = bubbleSortAsc(arr4);
      int[] sortedArr4_2 = bubbleSortDesc(arr4);
      Assertions.assertArrayEquals(new int[]{}, sortedArr4_1);
      Assertions.assertArrayEquals(new int[]{}, sortedArr4_2);

      int[] arr5 = {60, 20, 70, 10, 80, 30, 50, 40};
      int[] sortedArr5_1 = bubbleSortAsc(arr5);
      int[] sortedArr5_2 = bubbleSortDesc(arr5);
      Assertions.assertArrayEquals(new int[]{10, 20, 30, 40, 50, 60, 70, 80}, sortedArr5_1);
      Assertions.assertArrayEquals(new int[]{80, 70, 60, 50, 40, 30, 20, 10}, sortedArr5_2);

   }

   public static int[] bubbleSortAsc(int[] array){
       int[] arranged = Arrays.copyOf(array, array.length);
       boolean exchange;

       for(int i =0; i< array.length- 1; i++){
          exchange = false;
          for(int j =0; j < array.length -1 -i; j++){
             if (arranged[j] > arranged[j+1]){
                swap(arranged, j);
                exchange = true;
             }
          }
          if (!exchange){
             break;
          }

       }
       return arranged;
   }

   public static int[] bubbleSortDesc(int[] array) {
      int[] arranged = Arrays.copyOf(array, array.length);

      for (int i = 0; i < array.length-1; i++) {
         for (int j = 0; j < array.length -1 - i; j++) {
            if (arranged[j] < arranged[j + 1]) {
               swap(arranged, j);
            }
         }
      }
      return arranged;
   }

   private static void swap(int[] array, int i) {
      int temp = array[i];
      array[i] = array[i+1];
      array[i+1] = temp;
   }

}