버블 정렬(Bubble Sort)

정렬은 컴퓨터 과학에서 중요한 주제 중 하나이며, 여러 가지 알고리즘을 사용하여 데이터를 정렬할 수 있습니다. 이번 글에서는 자바에서

사용되는 간단하면서도 기본적인 정렬 알고리즘 중 하나인 버블 정렬(Bubble Sort)에 대해 알아보겠습니다.

 

버블 정렬(Bubble Sort) 개요

버블 정렬은 인접한 두 원소를 비교하여 필요에 따라 위치를 교환하는 간단한 정렬 알고리즘입니다. 이 알고리즘은 반복문을 사용하여 배열의 원소를 비교하고 필요한 경우 위치를 바꿔가면서 정렬을 수행합니다.

 

버블 정렬 알고리즘 동작 방식

아래는 버블 정렬 알고리즘의 기본 동작 방식입니다.

1. 배열의 첫 번째 원소부터 시작하여 인접한 두 원소를 비교합니다.
2. 만약 두 원소가 정렬 순서와 일치하지 않으면 위치를 교환합니다.
3. 배열의 끝까지 이동한 후, 가장 큰 원소가 배열의 마지막 위치에 위치합니다.
4. 다음 반복에서는 배열의 마지막 위치를 제외하고 위의 과정을 반복합니다.
5. 정렬이 완료될 때까지 이러한 반복을 수행합니다.

버블 정렬의 자바 코드

이제 실제로 자바 코드로 버블 정렬을 구현해보겠습니다.

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; 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;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arrayToSort = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arrayToSort);

        System.out.println("정렬된 배열:");
        for (int num : arrayToSort) {
            System.out.print(num + " ");
        }
    }
}

 

버블 정렬의 시간 복잡도

버블 정렬은 간단하고 이해하기 쉬우며, 작은 데이터셋에 대해 효과적입니다. 그러나 대규모 데이터에 대해서는 비효율적이며, 시간 복잡도가 O(n^2)입니다. 따라서 대규모 데이터에 대해 사용하기에는 다른 정렬 알고리즘들이 더 효율적일 수 있습니다.