Bubble sort(버블 정렬) - O(n2) (효율적인 코드 추가)

이름이 귀여운 bubble sort는

배열에서 i번째 요소와 (i + 1)번째 요소 값의 크기를 비교한 후 

i번째 요소의 값이 (i + 1)번째 요소의 값보다 크다면 서로 자리를 바꾸어 주는 방식의 정렬법 입니다. 

 

두 요소 중에 작은 값이 수면 위로 버블처럼 떠오르는 장면을 생각하면, 왜 이름이 버블 정렬인지 알 수 있을 것 같습니다. 

 

배열의 모든 요소를 반복해서 돌며 다 확인하기 때문에 시간 복잡도가 O(n2)입니다. 

 

- 사용:

          ① 배열의 규모가 작을 때 적합

          ② 구현이 비교적 간단

- 시간 복잡도: O(n2)

 

- 구현 코드: 

 

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

 

버블 솔트를 사용하게 되면, 가장 뒤부터 정렬이 된 수가 놓이게 됩니다. 앞에서 부터 하나씩 하나씩 수를 뒤로 옮겨놓기 때문이죠! 

그래서 안쪽 for loop을 돌 때 이미 정렬된 뒤의 수들은 다시 확인할 필요가 없어집니다.

그렇기 때문에 안쪽 for loop의 범위를 arr.length - i -1 로 지정하는 것입니다. 예를 들어서 arr.length = 5로 가정하고, for loop을 돌아보면 i  = 0 일 때는 j 가 0 <= j < (5 - 0 - 1) 범위일 것입니다. i = 1일 때는  j 가 0 <= j < (5 - 1 - 1)일 것이고 i = 2일 때는  j 가 0 <= j < (5 - 2 - 1) ... 이렇게 나아갑니다. 그러면 j가 도는 범위가 뒤에서부터 하나씩 줄어드는 게 보이시죠? 

이 부분만 잘 이해하면 사용에 어려움이 없을 것 같습니다!

 

 

구현 method 사용(아래)

 

  
public static void main(String[] args) {
 
 
     int[] unsortedArr = {89,5,76,1,2,45,23,99,54,11,67,1}; //정렬 전
 
     bubbleSort(unsortedArr); //정렬 후
 
     System.out.println(Arrays.toString(unsortedArr));
 
     //Prints [1, 1, 2, 5, 11, 23, 45, 54, 67, 76, 89, 99]
 
}
 

 

---

+ 정렬 시도 시 아무런 변화가 없는 경우는 이미 정렬이 완료된 것으로 판단하고 더 이상 정렬 시도를 안하게 할 수도 있습니다.

 

public static int[] bubbleSort(int[] arr) {
 
 
        for(int i = 0; i < arr.length; i++) {
            
            //boolean type으로 flag를 사용해 변화가 있었는지 확인해 줄 것입니다.
            boolean flag = false;
 
            for(int j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j+1]) {
                    swap(j, j+1, arr);
                    
                    //swap이 한번이라도 있었다면 flag를 true로 바꾸어 줍니다.
                    flag = true;
                }
            }
 
            //정렬 시도 했을 때 flag가 true로 바뀌지 않았다면 이미 정렬이 완료된 상태이므로
            //추가적인 정렬시도를 하지 않도록 for문을 빠져나옵니다.
            if(!flag) break;
        }
        return arr;
    }
 
    //swap이 일어나는 부분도 별도의 method로 빼놓을 수 있습니다.
    private static int[] swap(int a, int b, int[] arr) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
        return arr;
    }
 
}

 

이렇게 하면 불필요한 과정을 줄여 좀 더 빠르게 정렬할 수 있겠죠?