[자바 (JAVA)] 20. 버블 정렬

STEP 1.

package algo;

// {1,2,3,5,4}
public class Bubble02 {
    public static void main(String[] args) {
        // 인접한 두 수를 비교하고 교환
        int[] arr = {5, 3, 1, 2, 4};


        // 회전수는 N-1
        // 1회전 (목표 : 4번지의 값을 정하는 것)

        // 1-1 ---------------------------------------
        if (arr[0] > arr[1]) { // 교환 조건
            int temp = arr[1]; // temp = 3;
            arr[1] = arr[0];
            arr[0] = temp;
        }
        // {3,5,1,2,4}

        // 1-2 ----------------------------------------
        if (arr[1] > arr[2]) { // 교환 조건
            int temp = arr[2];
            arr[2] = arr[1];
            arr[1] = temp;
        }
        // {3,1,5,2,4}

        // 1-3
        if (arr[2] > arr[3]) { // 교환 조건
            int temp = arr[3];
            arr[3] = arr[2];
            arr[2] = temp;
        } // {3,1,2,5,4}

        // 1-4
        if (arr[3] > arr[4]) { // 교환 조건
            int temp = arr[4];
            arr[4] = arr[3];
            arr[3] = temp;
        } // {3,1,2,4,5}


        // 2회전 (목표 : 3번지의 값을 정하는 것)

        // 3회전 (목표 : 2번지의 값을 정하는 것)

        // 4회전 (목표 : 1번지의 값을 정하는 것)
    }
}

STEP 2. 1회전 공통 모듈 찾기

package algo;

// {1,2,3,5,4}
public class Bubble03 {
    public static void main(String[] args) {
        // 인접한 두  수를 비교하고 스왑(교환)
        int[] arr = {5, 3, 1, 2, 4};

        // 회전수는 N-1
        // 1회전 (목표 : 4번지의 값을 정하는 것)
        int a = 0;

        for (int i = 0; i < 4; i++) {

            if (arr[a] > arr[a + 1]) { // 교환 조건
                int temp = arr[a + 1]; // temp = 3;
                arr[a + 1] = arr[a];
                arr[a] = temp;
            }
            a++;
        }
        for (int i = 0; i < 5; i++) {
            System.out.print(arr[i] + ",");
        }
        System.out.println();


        // 2회전 (목표 : 3번지의 값을 정하는 것)


        // 3회전 (목표 : 2번지의 값을 정하는 것)


        // 4회전 (목표 : 1번지의 값을 정하는 것)


    }
}

3. 전체 회전 공통 모듈 찾기

package algo;

// {1,2,3,5,4}
// 공통 모듈 찾아내기
public class Bubble04 {
    public static void main(String[] args) {
        // 인접한 두 수를 비교하고 스왑(교환)
        int[] arr = {5, 4, 3, 2, 1}; // 샘플 최악으로 변경하기
        int a = 0; // 탐색 시작 index
        int n = arr.length; // 배열의 크기
        int r = 0; // 라운드
        int c = 0; // 라운드마다 반복 횟수

        // 회전수는 N-1
        // 1(r)회전 (목표 : 4번지의 값을 정하는 것)-------------------------------
        r++;
        a = 0;
        c = n - r; // 4
        for (int i = 0; i < c; i++) {

            if (arr[a] > arr[a + 1]) { // 교환 조건
                int temp = arr[a + 1]; // temp = 3;
                arr[a + 1] = arr[a];
                arr[a] = temp;
            }
            a++;
        }
        for (int i = 0; i < 5; i++) {
            System.out.print(arr[i] + ", ");
        }
        System.out.println();

        // 2회전 (목표 : 3번지의 값을 정하는 것)-------------------------------
        r++;
        a = 0;
        c = n - r; // 3

        for (int i = 0; i < c; i++) {

            if (arr[a] > arr[a + 1]) { // 교환 조건
                int temp = arr[a + 1]; // temp = 3;
                arr[a + 1] = arr[a];
                arr[a] = temp;
            }
            a++;
        }
        for (int i = 0; i < 5; i++) {
            System.out.print(arr[i] + ", ");
        }
        System.out.println();

        // 3회전 (목표 : 2번지의 값을 정하는 것)-------------------------------
        r++;
        a = 0;
        c = n - r; // 2

        for (int i = 0; i < c; i++) {

            if (arr[a] > arr[a + 1]) { // 교환 조건
                int temp = arr[a + 1]; // temp = 3;
                arr[a + 1] = arr[a];
                arr[a] = temp;
            }
            a++;
        }
        for (int i = 0; i < 5; i++) {
            System.out.print(arr[i] + ", ");
        }
        System.out.println();

        // 4회전 (목표 : 1번지의 값을 정하는 것)-------------------------------
        r++;
        a = 0;
        c = n - r; // 1

        for (int i = 0; i < c; i++) {

            if (arr[a] > arr[a + 1]) { // 교환 조건
                int temp = arr[a + 1]; // temp = 3;
                arr[a + 1] = arr[a];
                arr[a] = temp;
            }
            a++;
        }
        for (int i = 0; i < 5; i++) {
            System.out.print(arr[i] + ", ");
        }
        System.out.println();

    }
}

4. 반복

package algo;

// {1,2,3,5,4}
// 공통 모듈 찾아내기
public class Bubble05 {
    public static void main(String[] args) {
        // 인접한 두 수를 비교하고 스왑(교환)
        int[] arr = {5, 4, 3, 2, 1}; // 샘플 최악으로 변경하기
        int a = 0; // 탐색 시작 index
        final int N = arr.length; // 배열의 크기
        int r = 0; // 라운드
        int c = 0; // 라운드마다 반복 횟수

        // 회전수는 N-1
        // 1(r)회전 (목표 : 4번지의 값을 정하는 것)-------------------------------
        for (int round = 0; round < N - 1; round++) {
            r++;
            a = 0;
            c = N - r; // 4,3,2,1
            for (int i = 0; i < c; i++) {

                if (arr[a] > arr[a + 1]) { // 교환 조건
                    int temp = arr[a + 1]; // temp = 3;
                    arr[a + 1] = arr[a];
                    arr[a] = temp;
                }
                a++;
            }
            for (int i = 0; i < 5; i++) {
                System.out.print(arr[i] + ", ");
            }
            System.out.println();
        }
    }
}

5. 시간 복잡도 계산

package algo;

public class Bubble {
    public static void main(String[] args) {
        // 1. 초기 세팅
        int[] arr = {15, 13, 12, 11, 7, 10, 9, 8};

        int a; // 시작 index
        final int N = arr.length; // 배열의 크기
        int r = 0;

        // 시간복잡도
        // 첫항 : 1, 마지막항 N-1
        // 가우스연산 (끝)
        int myCount = Util.gauss(1, N - 1);
        System.out.println("myCount : " + myCount);

        int count = 0;

        for (int k = 0; k < N - 1; k++) {
            a = 0;
            r++;
            for (int i = 0; i < N - r; i++) {
                count++;
                System.out.print(".");
                if (arr[a] > arr[a + 1]) { // 교환 조건
                    int temp = arr[a + 1]; // temp = 3;
                    arr[a + 1] = arr[a];
                    arr[a] = temp;
                }
                a++;
            }
            for (int i = 0; i < N; i++) {
                System.out.print(arr[i] + ", ");
            }
            System.out.println();
        }
        System.out.println("시간복잡도 : 배열크기(" + N + ") : " + count);

    }
}

6. 버블 정렬 시간 복잡도 증명

버블정렬 시간복잡도 O((n^2-n) / 2) = O(n^2)
증명
n = 2일때 1번
n = 3일때 3번 (1+2)
n = 4일때 6번 (1+2+3)
n = 5일때 10번 (1+2+3+4)
n = 6일때 15번 (1+2+3+4+5)
.....
n일 때 (1+2+3+...+n-1) 번
총 더하는 횟수 : n-1번 (항의 수)
첫 항 : 1
마지막 항 : n-1
가우스 연산 적용 : 합 S = (첫 항 a + 마지막 항 l) * 항의 수 n / 2
(n-1 + 1) * (n-1) / 2 = n(n-1) / 2