<JAVA/자바> 버블정렬(Bubble Sort)

박상후·2024년 12월 29일

알고리즘

목록 보기

3/3

💡 개념

버블 정렬이란, 정렬되지 않은 데이터들 중 인접한 두 데이터를 비교해 자리를 교환해나가는 정렬 방식이다.
(처음 기준 위치는 0번 인덱스를 가르킨다.)

📌 과정

출처: algorithmcanvas

기준 위치와 다음 위치를 비교하여 기준 위치가 더 큰 값이라면
다음 위치로 변경한다.

(만약, 다음 위치가 더 크다면 pass)

초기 배열:
[ 38, 5, 57, 21, 12 ]

1회 정렬

단계	배열 상태	비교 요소	교환 여부	결과 배열 상태
1단계	[ 38, 5, 57, 21, 12 ]	(38, 5)	교환 O	[ 5, 38, 57, 21, 12 ]
2단계	[ 5, 38, 57, 21, 12 ]	(38, 57)	교환 X	[ 5, 38, 57, 21, 12 ]
3단계	[ 5, 38, 57, 21, 12 ]	(57, 21)	교환 O	[ 5, 38, 21, 57, 12 ]
4단계	[ 5, 38, 21, 57, 12 ]	(57, 12)	교환 O	[ 5, 38, 21, 12, 57 ]

결과:
1회 정렬 후 가장 큰 원소 57이 맨 뒤로 이동.
[ 5, 38, 21, 12, 57 ]

2회 정렬

1회 정렬의 결과로 57이 마지막 인덱스에 위치했으므로 이를 제외한 나머지 원소들만 정렬 진행.

단계	배열 상태	비교 요소	교환 여부	결과 배열 상태
1단계	[ 5, 38, 21, 12, 57 ]	(5, 38)	교환 X	[ 5, 38, 21, 12, 57 ]
2단계	[ 5, 38, 21, 12, 57 ]	(38, 21)	교환 O	[ 5, 21, 38, 12, 57 ]
3단계	[ 5, 21, 38, 12, 57 ]	(38, 12)	교환 O	[ 5, 21, 12, 38, 57 ]

결과:
2회 정렬 후 비교 범위 중 가장 큰 원소 38이 해당 범위의 마지막 인덱스로 이동.
[ 5, 21, 12, 38, 57 ]

3회 정렬

2회 정렬의 결과로 38, 57이 마지막 인덱스에 위치했으므로 이를 제외한 나머지 원소들만 정렬 진행.

단계	배열 상태	비교 요소	교환 여부	결과 배열 상태
1단계	[ 5, 21, 12, 38, 57 ]	(5, 21)	교환 X	[ 5, 21, 12, 38, 57 ]
2단계	[ 5, 21, 12, 38, 57 ]	(21, 12)	교환 O	[ 5, 12, 21, 38, 57 ]

결과:
3회 정렬 후 비교 범위 중 가장 큰 원소 21이 해당 범위의 마지막 인덱스로 이동.
[ 5, 12, 21, 38, 57 ]

4회 정렬

3회 정렬의 결과로 21, 38, 57이 마지막 인덱스에 위치했으므로 이를 제외한 나머지 원소들만 정렬 진행.

단계	배열 상태	비교 요소	교환 여부	결과 배열 상태
1단계	[ 5, 12, 21, 38, 57 ]	(5, 12)	교환 X	[ 5, 12, 21, 38, 57 ]

결과:
4회 정렬 후 비교 범위 중 가장 큰 원소 12가 해당 범위의 마지막 인덱스로 이동.
[ 5, 12, 21, 38, 57 ]

👨‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * [입력 데이터]
 * 1. 원소 개수
 * 2. 원소
 *
 * 5
 * 12 5 38 21 57
 */
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static int N;
    static int[] bubbleSort;

    public static void main(String[] args) throws IOException {
        init();

        // 마지막 원소는 자동 정렬되므로 n-1 반복
        for (int compareCount = 0; compareCount < N - 1; compareCount++) {

            /** [N - compareCount 이유]
             * 마지막 인덱스 부터 각 회전 횟수만큼 큰 값이 들어오므로 끝까지 비교할 필요가 없다.
             * 
             * [ N - compareCount - 1 이유]
             * 언제나 idx + 1 과 비교하기 때문에 고정적으로 마지막 자리는 비교할 필요가 없다.
             */
            for (int idx = 0; idx < N - compareCount - 1; idx++) {
                if (bubbleSort[idx] > bubbleSort[idx + 1]) {
                    int tmp = bubbleSort[idx];
                    bubbleSort[idx] = bubbleSort[idx + 1];
                    bubbleSort[idx + 1] = tmp;
                }
            }
        }

        for (int idx = 0; idx < N; idx++) {
            sb.append(bubbleSort[idx]).append(" ");
        }

        System.out.println(sb);
    }

    public static void init() throws IOException {
        N = Integer.parseInt(br.readLine().trim());

        st = new StringTokenizer(br.readLine().trim());
        bubbleSort = new int[N];
        for (int idx = 0; idx < N; idx++) {
            bubbleSort[idx] = Integer.parseInt(st.nextToken());
        }
    }
}

⏱️ 시간복잡도

비교 연산

첫 번째 루프에서는 N-1번의 비교가 이루어진다.
두 번째 루프에서는 N-2번의 비교, 세 번째 루프에서는 N-3번의 비교, ..., 마지막 루프에서는 1번의 비교가 이루어진다.
따라서 총 비교 횟수는 다음과 같다. $(N-1) + (N-2) + (N-3) + \dots + 1 = \frac{N(N-1)}{2}$
즉, O(N²) 로 표현할 수 있다.

교환 연산

최악의 경우, N-1번의 교환 연산이 각 비교마다 발생할 수 있다.
교환 연산의 시간 복잡도는 O(1) 이므로, 전체 시간 복잡도는 비교 연산의 복잡도에 의해 결정된다.

결론

최선의 경우: 이미 정렬된 배열에서는 O(N) 만큼의 비교만 발생한다.
평균 및 최악의 경우: 비교 연산이 O(N²) 에 해당하며, 이는 시간복잡도의 상한을 결정한다.

📖 선택정렬과 비교

버블 정렬과 선택 정렬은 모두 평균 및 최악의 경우 시간복잡도가 O(N²) 로 동일하지만, 동작 방식에서 차이가 있습니다.

비교와 교환 방식의 차이

버블 정렬
- 인접한 두 요소를 비교한 뒤, 필요하다면 교환합니다.
- 한 번의 내부 루프가 끝날 때마다 가장 큰(혹은 작은) 값이 정렬된 위치로 이동합니다.
- 교환 연산이 자주 발생하며, 최선의 경우(이미 정렬된 경우) 교환이 전혀 이루어지지 않아 시간복잡도가 O(N) 이 됩니다.
선택 정렬
- 각 패스에서 최솟값(혹은 최댓값)을 찾아 한 번만 교환합니다.
- 비교 연산은 많지만, 교환은 패스당 한 번만 이루어집니다.
- 최선의 경우에도 비교와 교환이 모두 필요하므로 항상 O(N²) 의 시간복잡도를 가집니다.

교환 연산 횟수

버블 정렬
- 비교 연산과 동시에 교환이 이루어질 수 있어, 교환 연산이 빈번하게 발생합니다.
- 교환 연산이 많기 때문에 데이터가 클 경우 상대적으로 더 비효율적입니다.
선택 정렬
- 패스마다 최대 한 번의 교환만 발생하므로, 전체 교환 횟수가 버블 정렬보다 적습니다.

최선의 경우 성능

버블 정렬
- 이미 정렬된 배열에서는 교환이 필요 없기 때문에 비교만 진행하며 O(N) 의 성능을 보여줍니다.
선택 정렬
- 최선의 경우에도 모든 원소를 비교하여 최솟값을 찾기 때문에 항상 O(N²) 의 시간복잡도를 가집니다.

결론

버블 정렬은 데이터가 이미 정렬되어 있을 가능성이 높은 경우 유리합니다.
반면, 선택 정렬은 교환 연산이 적기 때문에 데이터 교환의 비용이 큰 환경에서 더 효율적일 수 있습니다.

두 정렬 모두 단순하지만 비효율적인 정렬 방식이므로, 대규모 데이터에서는 퀵 정렬이나 병합 정렬 같은 고급 알고리즘을 사용하는 것이 더 적합합니다.

박상후

성장보다 성과를

이전 포스트