[정렬 뿌시기] - 버블정렬(Bubble Sort)

버블 정렬(Bubble Sort)란?
순차적으로 인접한 두개의 원소를 비교해나가면서 정렬하는 방법

버블 정렬의 알고리즘은?

(1) 1번 원소와 2번 원소를 비교 후 변경 또는 유지

(2) 2번 원소와 3번 원소를 비교 후 변경 또는 유지

(3) 3번 원소와 4번 원소를 비교 후 변경 또는 유지

(4) 4번 원소와 5번 원소를 비교 후 변경 또는 유지

(5) 배열의 크기 -1 만큼의 비교 연산이 이루어진다면, 가장 큰 수가 마지막에 정렬될 것이다.

(6) 다시 처음으로 돌아와 1번 원소와 2번 원소를 비교 후 변경 또는 유지

(7) 2번 원소와 3번 원소를 비교 후 변경 또는 유지

계속해서 순차적으로 인접 원소와 비교해 나가게 되고 빨간 상자로 표시 된 마지막 수는 모든 원소와 비교 후에 가장 큰 수로 판단되었으므로 이후 정렬 연산에는 참여할 필요가 없다.

버블 정렬을 자바 코드로 구현해보기!

public class bubblesort {

    public static void main(String[] args) {

        int[] arr = {3,2,5,4,1};

        for(int i=0; i < arr.length; 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(int i=0; i<arr.length; i++){
            System.out.print(arr[i] + " ");
        }

    }

}

버블 정렬의 시간 복잡도
버블 정렬의 소스코드를 보면 최대 수를 찾기 위해 n-1번의 비교를 합니다. 그 후에는 n-2.. n-3.. 1번이 됩니다.
즉 n-1 + n-2 + n-3 + ---- + 1로 = (n)(n-1)/2번의 비교 연산을 수행하여 O(n^2)의 시간 복잡도를 가집니다.

버블 정렬은 단순하게 구현할 수 있지만 퀵 정렬, 힙 정렬, 합병 정렬 등과 비교하면 비효율적인 정렬 방법입니다.
또한 베스트 케이스나, 워스트 케이스, 평균적인 케이스의 시간 복잡도 모두 n^2를 가지고 있는 알고리즘입니다.