Java알고리즘

[JAVA] 8. 필수 알고리즘 Ⅹ. 버블정렬

최재원's avatar
최재원
Feb 13, 2025
[JAVA] 8. 필수 알고리즘 Ⅹ. 버블정렬
Contents
1. 사람이 하는 방법2. 코드로 정렬 구현 3. 변수 사용4. 반복문 사용
❗
  • 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
  • 선택 정렬과 기본 개념이 유사하다.
  • 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
  • 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

원리 및 등장 이유

  • 원리:
    • 배열의 인접한 두 요소를 차례대로 비교하여, 순서가 맞지 않으면 서로 교환합니다.
    • 한 번의 전체 순회가 끝나면 가장 큰(또는 작은) 값이 배열의 끝으로 이동합니다.
    • 이 과정을 반복하여 전체 배열이 정렬됩니다.
  • 등장 이유:
    • 이해하기 쉽고 구현이 간단하여 교육용이나 작은 데이터셋 정렬에 주로 사용됩니다.
    • 단, 시간 복잡도가 O(n²)로 큰 데이터셋에서는 비효율적입니다.

원리 다이어그램

초기 상태: [5, 3, 8, 4, 2]

비교 및 교환 과정:
[5, 3, 8, 4, 2]
  ^  ^
  비교: 5와 3 → 3 < 5 -> 교환
  
결과: [3, 5, 8, 4, 2]
      3, 5, 8, 4, 2
         ^  ^
         비교: 5와 8 → 순서 맞음
  
[3, 5, 8, 4, 2]
            ^  ^
            비교: 8와 4 → 교환

결과: [3, 5, 4, 8, 2]
[3, 5, 4, 8, 2]
               ^  ^
               비교: 8와 2 → 교환

결과: [3, 5, 4, 2, 8]   ← 8이 자리잡음 (첫번째 패스 완료)
자바코드 예시
public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            // 마지막 i개의 원소는 이미 정렬되어 있으므로 제외
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 두 값 교환
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            // 교환이 없으면 이미 정렬된 상태
            if (!swapped) break;
        }
    }
    
    public static void main(String[] args) {
        int[] data = {5, 3, 8, 4, 2};
        bubbleSort(data);
        for (int num : data) {
            System.out.print(num + " ");
        }
    }
}

1. 사람이 하는 방법

package algo;

// 정렬
// 1.버블
// 2.삽입
// 3.선택
// 4.퀵솔트

// <버블정렬>
// 오름차순
// [1,4,2,6] -> [1,2,4,6]
// 내림차순
// [1,4,2,6] -> [6,4,2,1]
public class Bubble01 {
    public static void main(String[] args) {
        int[] arr = {5, 3, 1, 2, 4};
        int[] newArr = new int[5];

        // 1. 1라운드
        newArr[0] = arr[2];

        // 2. 2라운드
        newArr[1] = arr[3];

        // 3. 3라운드
        newArr[2] = arr[1];

        // 4. 4라운드
        newArr[3] = arr[4];

        // 5. 5라운드
        newArr[4] = arr[0];

        for (int i = 0; i < 5; i++) {
            System.out.print(newArr[i]);
        }
    }
}
notion image

2. 코드로 정렬 구현 

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];
            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번지의 값을 정하는 것)
        // 2-1--------------------------------------
        if (arr[0] > arr[1]) { // 교환조건
            int temp = arr[1];
            arr[1] = arr[0];
            arr[0] = temp;
        }
        // {1,3,2,4,5}
        // 2-2--------------------------------------
        if (arr[1] > arr[2]) { // 교환조건
            int temp = arr[2];
            arr[2] = arr[1];
            arr[1] = temp;
        }
        // {1,2,3,4,5}
        // 2-3--------------------------------------
        if (arr[2] > arr[3]) { // 교환조건
            int temp = arr[3];
            arr[3] = arr[2];
            arr[2] = temp;
        }
        // {1,2,3,4,5}
        // 3회전 (목표 : 2번지의 값을 정하는 것)
        // 3-1--------------------------------------
        if (arr[0] > arr[1]) { // 교환조건
            int temp = arr[1];
            arr[1] = arr[0];
            arr[0] = temp;
        }
        // {1,2,3,4,5}
        // 3-2--------------------------------------
        if (arr[1] > arr[2]) { // 교환조건
            int temp = arr[2];
            arr[2] = arr[1];
            arr[1] = temp;
        }
        // {1,2,3,4,5}
        // 4회전 (목표 : 1번지의 값을 정하는 것)
        // 4-1--------------------------------------
        if (arr[0] > arr[1]) { // 교환조건
            int temp = arr[1];
            arr[1] = arr[0];
            arr[0] = temp;
        }
        // {1,2,3,4,5}
        for (int i = 0; i < 5; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
notion image

3. 변수 사용

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번지의 값을 정하는 것)
        // 1-1--------------------------------------
        int a = 0; // 탐색 인덱스
        if (arr[a] > arr[a + 1]) { // 교환조건
            int temp = arr[a + 1];
            arr[a + 1] = arr[a];
            arr[a] = temp;
        }
        a++;
        // {3,5,1,2,4}

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

        // 1-3--------------------------------------
        if (arr[a] > arr[a + 1]) { // 교환조건
            int temp = arr[a + 1];
            arr[a + 1] = arr[a];
            arr[a] = temp;
        }
        a++;
        // {3,1,2,5,4}
        // 1-4--------------------------------------
        if (arr[a] > arr[a + 1]) { // 교환조건
            int temp = arr[a + 1];
            arr[a + 1] = arr[a];
            arr[a] = temp;
        }
        a++;
        // {3,1,2,4,5}
        // 2회전 (목표 : 3번지의 값을 정하는 것)
        // 2-1--------------------------------------
        a = 0;
        if (arr[a] > arr[a + 1]) { // 교환조건
            int temp = arr[a + 1];
            arr[a + 1] = arr[a];
            arr[a] = temp;
        }
        // {1,3,2,4,5}
        // 2-2--------------------------------------
        a++;
        if (arr[a] > arr[a + 1]) { // 교환조건
            int temp = arr[a + 1];
            arr[a + 1] = arr[a];
            arr[a] = temp;
        }
        // {1,2,3,4,5}
        // 2-3--------------------------------------
        if (arr[a] > arr[a + 1]) { // 교환조건
            int temp = arr[a + 1];
            arr[a + 1] = arr[a];
            arr[a] = temp;
        }
        // {1,2,3,4,5}
        // 3회전 (목표 : 2번지의 값을 정하는 것)
        // 3-1--------------------------------------
        if (arr[a] > arr[a + 1]) { // 교환조건
            int temp = arr[a + 1];
            arr[a + 1] = arr[a];
            arr[a] = temp;
        }
        // {1,2,3,4,5}
        // 3-2--------------------------------------
        if (arr[a] > arr[a + 1]) { // 교환조건
            int temp = arr[a + 1];
            arr[a + 1] = arr[a];
            arr[a] = temp;
        }
        // {1,2,3,4,5}
        // 4회전 (목표 : 1번지의 값을 정하는 것)
        // 4-1--------------------------------------
        if (arr[a] > arr[a + 1]) { // 교환조건
            int temp = arr[a + 1];
            arr[a + 1] = arr[a];
            arr[a] = temp;
        }
        // {1,2,3,4,5}
        for (int i = 0; i < 5; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

4. 반복문 사용 

package algo;

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

        // 회전수 = n - 1;
        // 1회전 (목표 : 4번지의 값을 정하는 것)
        // 1-4
        int n = 5; // 배열의 길이
        int r = n - 1; // 교환 횟수
        int a = 0; // 탐색 인덱스
        for (int i = 0; i < r; i++) {
            if (arr[a] > arr[a + 1]) { // 교환조건
                int temp = arr[a + 1];
                arr[a + 1] = arr[a];
                arr[a] = temp;
            }
            a++;
        }
        r = r - 1;
        // {3,1,2,4,5}
        // 2회전 (목표 : 3번지의 값을 정하는 것)
        // 2-1--------------------------------------
        a = 0;
        for (int i = 0; i < r; i++) {
            if (arr[a] > arr[a + 1]) { // 교환조건
                int temp = arr[a + 1];
                arr[a + 1] = arr[a];
                arr[a] = temp;
            }
            a++;
        }
        r = r - 1;
        // {1,2,3,4,5}
        // 3회전 (목표 : 2번지의 값을 정하는 것)
        // 3-1--------------------------------------
        a = 0;
        for (int i = 0; i < r; i++) {
            if (arr[a] > arr[a + 1]) { // 교환조건
                int temp = arr[a + 1];
                arr[a + 1] = arr[a];
                arr[a] = temp;
            }
            a++;
        }
        r = r - 1;
        // {1,2,3,4,5}
        // 4회전 (목표 : 1번지의 값을 정하는 것)
        // 4-1--------------------------------------
        a = 0;
        for (int i = 0; i < r; i++) {
            if (arr[a] > arr[a + 1]) { // 교환조건
                int temp = arr[a + 1];
                arr[a + 1] = arr[a];
                arr[a] = temp;
            }
            a++;
        }
        r = r - 1;
        // {1,2,3,4,5}
    }
}

package algo;

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

        // 회전수 = n - 1;
        int n = 5; // 배열 갯수
        int r = n - 1; // 교환 횟수
        int a; // 탐색 인덱스
        for (int i = 0; i < n - 1; i++) {
            a = 0;
            for (int j = 0; j < r; j++) {
                if (arr[a] > arr[a + 1]) { // 교환조건
                    int temp = arr[a + 1];
                    arr[a + 1] = arr[a];
                    arr[a] = temp;
                }
                a++;
            }
            r = r - 1;
        }
        // {1,2,3,4,5}
    }
    System.out.println("시간복잡도 : 배열크기(" + n + ") : " + count);
}
notion image
 
Share article

More articles

See more posts

[JAVA] 9. 최종테스트(로또)

February 13, 2025
[JAVA] 9. 최종테스트(로또)

[JAVA] 8. 필수 알고리즘 Ⅺ. 퀵솔트

February 13, 2025
[JAVA] 8. 필수 알고리즘 Ⅺ. 퀵솔트

[JAVA] 8. 필수 알고리즘 Ⅸ. 피보나치 수열

February 13, 2025
[JAVA] 8. 필수 알고리즘 Ⅸ. 피보나치 수열

[JAVA] 8. 필수 알고리즘 Ⅷ. 시계 연산

February 12, 2025
[JAVA] 8. 필수 알고리즘 Ⅷ. 시계 연산

jjack1

RSS·Powered by Inblog