버블정렬

특징

• 안정정렬 (stable sort) 이다 
• 추가적인 공간이 필요하지 않은 제자리 정렬( in-place sort ) 이다

시간복잡도

장점

1. 구현이 매우 쉽다.
2. 추가적인 메모리 소비가 적다.
3. 안정정렬이다.

단점

1. 정렬하는데 오랜시간이 걸린다. (시간복잡도가 높다)

정렬방법

1. 현재 원소와 다음 원소를 비교한다.
2. 현재 원소 > 다음 원소 이면 둘의 위치를 바꾼다.
3. 다음 원소로 이동한다.

유튜브 영상으로도 버블정렬을 확인할 수 있습니다.

자바로 구현

기본 버블정렬

public class Bubble_Sort {

    public static void main(String[] args) {
        int[] array = {5, 3, 1, 4, 2};
        System.out.printf("초기배열 : {%d, %d, %d, %d, %d} \n", array[0], array[1], array[2], array[3], array[4]);
        bubble_sort(array);
        System.out.printf("정렬된배열 : {%d, %d, %d, %d, %d} \n", array[0], array[1], array[2], array[3], array[4]);
    }

    private static void bubble_sort(int[] array) {
        // i 는 위 그림의 Round와 같음
        for (int i = 1; i < array.length; i++) {

            // Round별 비교횟수는 Round가 증가함에 따라 횟수가 줄어듬
            for (int j = 0; j < array.length - i; j++) {

                // 현재원소가 다음원소보다 크다면 두개의 값을 변경한다.
                if (array[j] > array[j + 1]) {
                    swap(array, j);
                }
            }
        }
    }

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

최적화된 버블정렬

public class Bubble_Sort {

    public static void main(String[] args) {
        int[] array = {5, 3, 1, 4, 2};
        System.out.printf("초기배열 : {%d, %d, %d, %d, %d} \n", array[0], array[1], array[2], array[3], array[4]);
        bubble_sort(array);
        System.out.printf("정렬된배열 : {%d, %d, %d, %d, %d} \n", array[0], array[1], array[2], array[3], array[4]);
    }

    private static void bubble_sort(int[] array) {
        // i == 위 그림의 Round와 같음
        for (int i = 1; i < array.length; i++) {

            boolean isSwapped = false;

            // Round별 비교횟수는 Round가 증가함에 따라 횟수가 줄어듬
            for (int j = 0; j < array.length - i; j++) {

                // 현재원소가 다음원소보다 크다면 두개의 값을 변경한다.
                if (array[j] > array[j + 1]) {
                    swap(array, j);
                    isSwapped = true;
                }
            }

            // 비교과정에서 한번도 교환이 이루어지지않았다면 반복문 종료
            if (!isSwapped) {
                break;
            }

        }
    }

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