버블 정렬

[Java] 버블 정렬 알고리즘 작성

Dec 18, 2023

Contents

버블 정렬(bubble sort)

목표 : 오름차순을 기준으로 정렬

⚡

원본 데이터 (5, 8, 2, 4, 3) N

알고리즘 작성 해보기

1회전(4바퀴)

(1) 5, 8 비교 (변화 없음)

(2) 8, 2 비교 (5, 2, 8, 4, 3)

(3) 8, 4 비교 (5, 2, 4, 8, 3)

(4) 8, 3 비교 (5, 2, 4, 3, 8)

1회전을 수행하면 정렬이 완료되지는 않았지만 가장 끝 수가 맨 뒤로 이동

2회전(3바퀴)

(1) 5, 2 비교 (2, 5, 4, 3, 8)

(2) 5, 4 비교 (2, 4, 5, 3, 8)

(3) 5, 3 비교 (2, 4, 3, 5, 8)

2회전을 수행하면 그 다음으로 큰 수가 맨 뒤로 이동, 바퀴 수는 한 바퀴 줄어든다

3회전(2바퀴)

(1) 2, 4 비교 (2, 4, 3, 5, 8)

(2) 4, 3 비교 (2, 3, 4, 5, 8)

4회전(1바퀴)

(1) 2, 3 비교 변화 없음

회전수 : N-1 n회전 비교 횟수 : N-n

바퀴수가 줄어드는 코드 작성


package ex03.test;

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

        final int N = arr.length; // 길이는 변하지 않기 때문에 final을 넣어서 구분해줌.

        //첫번째 4바퀴 돌기
        for (int i = 0; i < N-1; i++) {
            for (int j = 0; j < N-i-1; j++) {
                System.out.println("몇바퀴 돌까?");
            }
            System.out.println();
        }

        // 두번째 4바퀴 도는데, 1회전때 4바퀴도는 내부 포문 만들기
    }
}

자리를 바꾸는 스왑코드 작성


package ex03.test;

public class BubbleTest03 {
    public static void main(String[] args) {
        int[] arr = {4,3};

        // 스왑코드
        int temp;
        temp = arr[0];
        arr[0] = arr[1];
        arr[1] = temp;

        System.out.println(arr[0]);
        System.out.println(arr[1]);

    }
}

1회전 코드 작성해보기


if(arr[0] > arr[1]){
		temp = arr[0];
		arr[0] = arr[1];
		arr[1] = temp;
}
if(arr[1] > arr[2]){
		temp = arr[1];
		arr[1] = arr[2];
		arr[2] = temp;
}
if(arr[2] > arr[3]){
		temp = arr[2];
		arr[2] = arr[3];
		arr[3] = temp;
}
if(arr[3] > arr[4]){
		temp = arr[3];
		arr[3] = arr[4];
		arr[4] = temp;
}

for문으로 다시 작성 해보기


package ex03.test;

import java.util.Arrays;

public class BubbleTest04 {
    public static void main(String[] args) {
        int[] arr = {5,8,2,4,3};
        final int N = arr.length;

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

바퀴수가 줄어드는 코드와 합쳐보기

최종


package ex03.test;

import java.util.Arrays;

public class BubbleTest05 {
    public static void main(String[] args) {
        int[] arr = {5,8,2,4,3};
        final int N = arr.length;

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