버블정렬 - 자바로 구현하기

| 버블정렬(Bubble Sort)이란?

• 간단한 정렬 알고리즘 중의 하나로 이름에서 알 수 있듯이, 이 알고리즘은 큰 값이 마칠 "버블"처럼 배열의 끝으로 "떠오르게"하는 방식으로 작동한다.

 

| 버블정렬(Bubble Sort)의 작동원리

1) 첫 번째 항목부터 마지막 항목까지 순차적으로 이동하면서 인접한 항목을 비교한다.

2) 인접한 두 항목을 비교하면서 왼쪽 항목이 오른쪽 항목보다 크면 두 항목의 위치를 바꾼다.

3) 위의 과정을 배열의 모든 항목에 대해 반복한다.

4) 위의 3단계를 배열의 항목 수만큼 반복하면 배열이 정렬된다.

 

예시) 1 5 3 9 7 배열이 버블 정렬되는 과정을 단계별로 살펴보겠습니다. 초기 배열 1 5 3 9 7 1차 반복 (i=0) 1과 5를 비교: 정렬이 필요하지 않습니다. 5와 3을 비교: 5가 3보다 크므로 위치를 바꿉니다. => 1 3 5 9 7 5와 9를 비교: 정렬이 필요하지 않습니다. 9와 7을 비교: 9가 7보다 크므로 위치를 바꿉니다. => 1 3 5 7 9 2차 반복 (i=1) 1과 3을 비교: 정렬이 필요하지 않습니다. 3과 5를 비교: 정렬이 필요하지 않습니다. 5와 7를 비교: 정렬이 필요하지 않습니다. 이 시점에서 추가적인 정렬이 필요하지 않기 때문에 버블 정렬은 종료됩니다. 따라서 최종 정렬된 배열은 1 3 5 7 9가 됩니다. 참고로, 이미 정렬된 부분(여기서는 9)을 다시 검사하지 않기 위해, 버블 정렬에서는 각 반복마다 검사해야 하는 배열의 길이가 하나씩 줄어듭니다.

 

| 버블정렬(Bubble Sort)의 특징

(시간 복잡도와 공간 복잡도 : https://sharonprogress.tistory.com/234)

• 시간복잡도 : 평균 및 최악의 경우 O(n^2) , n은 배열의 항목 수
• 공간 복잡도 : O(1)
• 안정적 정렬 : 동일한 값의 원래 순서가 정렬 후에도 유지된다.

 

| 버블정렬(Bubble Sort)의 사용

• 위의 특징들로 인해 대규모 데이터에는 적합하지 않으며, 효율적이지 않은 정렬 알고리즘의 하나로 간주된다. 실제 응용 프로그램에서는 보다 효율적인 알고리즘(퀵 정렬, 병합 정렬 등)이 주로 사용된다.

 

 

 

| 버블정렬(Bubble Sort) Java로 구현하기

• 아래 코드에서 'bubble Sort' 함수는 주어진 배열 'arr'을 버블 정렬한다.
• swapped라는 플래그를 사용하여 한 라운드에서 어떤 요소도 교환되지 않았다면 배열이 이미 정렬된 것으로 간주하고 더 이상의 정렬을 중단한다. 이는 버블 정렬의 성능을 약간 향상시키는 최적화 방법이다.

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("Sorted array:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            // If no two elements were swapped by inner loop, then break
            if (!swapped) {
                break;
            }
        }
    }
}