거품정렬(Bubble Sort)

거품정렬(Bubble Sort)

개념

Bubble Sort는 서로 인접한 두 원소의 대소를 비교하여 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘입니다.

로직

인접한 데이터 간에 교환이 계속일어나면서 정렬이 이루어지는 방법

1. 인접한 2개의 데이터를 비교하여 크기가 순서대로 정렬되어 있지 않으면 서로 교환한다
2. 교환이 이루어지지 않을 때까지 반복한다.

1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하는 특징이 있다.

코드

BubbleSort.java

아래 작성된 코드는 개선된 버전의 Bubble Sort이다.

1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하는 특징이 있기 때문에 탐색하는 범위를 줄였으며

버블정렬의 각 단계에서 데이터의 교환이 일어나지 않으면 정렬이 끝난 것을 의미하므로 다음단계를 실행하지 않고 정렬을 종료할 수 있다.

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class BubbleSort {
    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    private static void bubbleSort(int[] arr) {
        boolean flag = true;
        int temp;
        for (int n = arr.length - 1; n > 0 && flag; n--) {
            flag = false;
            for (int i = 0; i < n; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                    flag = true;
                }
            }
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

console

정렬 전: [75, 28, 51, 92, 75, 15, 45, 97, 70, 79]
정렬 후: [15, 28, 45, 51, 70, 75, 75, 79, 92, 97]

시간복잡도

비교 횟수

주어진 데이터의 개수가 $n$개 일때
$$
\sum_{i=1}^{n-1}n-i=(n-1)+(n-2)+(n-3)+...+1=\frac{n(n-1)}{2}
$$
번의 비교를 하게 된다.

최선, 최악, 평균 모두 $O(N^2)$의 동일한 시간복잡도를 갖습니다.

교환 횟수

최악의 경우 원소를 비교할때마다 자리 교환이 일어나므로 최대 ${n(n-1)\over2}$번의 교환이 발생합니다.

장점

1. 알고리즘이 단순하여 구현이 쉽다.
2. 추가적인 메모리 공간이 필요하지 않다.
3. 안정 정렬이다.

단점

1. 시간복잡도가 $O(N^2)$으로 비효율적이다.
2. 정렬 되어있지 않은 원소를 정렬하기 위해 교환(swap)이 많이 일어난다.
   • 같은 시간복잡도 Selection Sort는 1번의 교환으로 정렬이 가능하다.