Bubble Sort [거품정렬]

Bubble Sort [거품정렬]

performance : O(n^2)

space complexity : O(1)

* 시간복잡도가 O(n^2) 이므로 느리지만 코드가 단순하기 때문에 자주 사용된다고 한다.

거품정렬은 원소의 이동하는 모습이 거품이 수명으로 올라오는듯한 모습과 비슷하므로 지어진 이름이다.

해당 정렬의 목표는 인접한 두개의 자료를 비교해서 차순에 맞게 교환하는 작업을 정렬이 완료 될 때까지 해준다.

자료수에 한 개를 뺄 만큼 Looping을 하면서 서로 인접한 아이템을 swapping해주는 방법으로 해당 리스트를 정렬할 것이다. 즉, 아래와 같이총 4개의 아이템이 있으므로 우리는 총 3번(=n-1) Looping을 할 것이다. ( 예제 리스트: 6 5 3 1 )

[Loop Count : 1, Start List : 6 5 3 1]

1. 첫번째 아이템인 6보다 5가 작으니까 swapping한다. => 5 6 3 1 (Loop count = 1)   

2. 이동한 6보다 3이 작으니까 swapping한다. => 5 3 6 1 (Loop count = 1) 

3. 이동한 6보다 1이 작으니까 swapping한다. => 5 3 1 6 (Loop count = 1) 

[Loop Count : 2, Start List : 5 3 1 6]

1. 첫번째 아이템인 5보다 3이 작으니까 swapping한다. => 3 5 1 6 (Loop count = 2)

2. 이동한 5보다 1이 작으니까 swapping한다. => 3 1 5 6 (Loop count = 2)

3. 이동한 5보다 6이 크므로 swapping이 일어나질 않는다. => 3 1 5 6 (Loop count = 2)

[Loop Count : 3, Start List : 3 1 5 6]

1. 첫번째 아이템인 3보다 1이 작으니까 swapping한다. => 1 3 5 6 (Loop count = 3)

2. 이동한 3보다 5가 크므로 swapping이 일어나질 않는다. => 1 3 5 6 (Loop count = 3)

3. 위의 2번에서 비교한 3의 다음 아이템인 5보다 6이 크므로 swapping이 일어나질 않는다. => 1 3 5 6 (Loop count = 3)

[결론]

위의 과정대로 자료수-1 만큼 cycle을 했고, 결과는 보는 내용과 같이 1 3 5 6 이고 Loop Count는 3이다. 

[예제 소스]

/**
  * 해당 함수를 해석하면 인자로 받는 배열의 크기와 상관없이 언제나 일정한 속도로 값을 반환한다.
  * 이런 경우에 이 알고리즘을 "O(1)의 시간복잡도를 가진다"라고 표현한다.
*/
public class BubbleSortExample {
    static void bubbleSort(int[] arr) {
        int n = arr.length;
        int temp = 0;
        for(int i=0; i < n; i++){
            for(int j=1; j < (n-i); j++){
                if(arr[j-1] > arr[j]){ // 아이템 비교
                    //swap elements
                    temp = arr[j-1]; // (1) 위의 비교조건에 만족한다면 swapping을 해야하므로 좌측의 큰 숫자를 변수에 저장
                    arr[j-1] = arr[j]; // (2) 우측에 작은 숫자를 기존에 좌측에 큰 숫자가 있었던 배열 자리에 할당
                    arr[j] = temp; // (3) 위의 (1)번에 담아둔 변수를 기존에 우측에 작은 숫자가 있었던 배열 자리에 할당
                }
            }
        }

        System.out.println("총 회전 수 : "+n);
    }
    public static void main(String[] args) {
        int arr[] ={4, 54, 2, 8, 63, 7, 55, 56};

        System.out.println("Array Before Bubble Sort");
        for(int i=0; i < arr.length; i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();

        bubbleSort(arr);//sorting array elements using bubble sort

        System.out.println("Array After Bubble Sort");
        for(int i=0; i < arr.length; i++){
            System.out.print(arr[i] + " ");
        }

    }
}