[JAVA] 버블 정렬(bubble sort)

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

• 인접한 2개의 레코드를 비교하여 크기가 큰 순서대로 돼 있지 않으면 서로를 교환

• 선택 정렬과 기본 개념이 유사하다.

구체적인 개념

• 버블정렬은 n번째 자료와 n+1자료를 비교하여 교환하면서 자료를 정렬한다.

• 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬

예제

• 1 회전을(loop 4) 하면 제일 큰 수가 제일 뒤로간다.

• 두번째 큰 수가 뒤에서 두번째로 간다.

• loop수가 1 줄었다.

예제로 코딩하기

public class BublbleTest01 {
    public static void main(String[] args) {
        int[] arr = { 5, 8, 2, 4, 3};
        int temp;

        for (int i = 1; i < arr.length ; i++) {
            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

다른 예제

public class BubbleEx01 {
    static void bubble(int[] arr) {
        final int N = arr.length;

        int temp;

        for (int loop = 1; loop < N; loop++) {
            for (int i = 0; i < N - loop; i++) {
                if (arr[i] > arr[i + 1]) {
                    temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            System.out.print(arr[i] + " ");
        }
    }
    public static void main(String[] args) {
        int[] arr = { 5, 8, 2, 4, 3};
        BubbleEx01.bubble(arr);
        System.out.println();
        
        int[] arr2 = { 5, 8, 2, 4, 3, 10, 500, 7 ,6 ,1};
        bubble(arr2); // BubbleEx01. 같은 class 안에 있으면 생략가능

    }
}