버블 정렬 (Bubble Sort)

버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)에 대해 알아보겠습니다. 이름에서 알 수 있듯이, 버블 정렬은 마치 '거품'처럼 큰 값이 오른쪽으로 올라가는 방식의 정렬 알고리즘입니다. 버블 정렬의 동작은 인접한 두 원소를 비교하여 큰 값을 오른쪽으로, 작은 값을 왼쪽으로 이동시키는 과정을 반복하는 것입니다. 이 과정은 배열의 끝까지 계속 이어지며, 이를 통해 모든 원소들을 정렬하게 됩니다. 이런 과정을 상상하면, 마치 물 속에서 거품이 올라가듯이 큰 값이 오른쪽으로, 즉 배열의 끝으로 이동하는 것을 볼 수 있습니다.

 

아래는 버블 정렬의 동작 과정을 나타낸 그림입니다.

 

출처: https://en.wikipedia.org/wiki/Bubble_sort#Example

1. 배열의 첫 원소와 두 번째 원소를 비교하여 큰 값을 오른쪽으로 이동시킵니다.
2. 두 번째 원소와 세 번째 원소를 비교하여 큰 값을 오른쪽으로 이동시킵니다.
3. 이 같은 과정을 배열의 끝까지 반복합니다.
4. 배열의 마지막 원소까지 이 과정을 반복하면, 가장 큰 값이 배열의 마지막으로 이동하게 됩니다.
5. 다시 처음부터 위의 과정을 반복합니다.

이렇게 반복하는 과정을 통해 배열의 모든 원소가 순서대로 정렬됩니다.

하지만, 버블 정렬의 시간 복잡도는 최선, 평균, 최악의 경우 모두 O(n^2)입니다. 이는 정렬할 데이터의 크기가 커질수록, 즉 n이 커질수록 성능이 급격히 떨어진다는 것을 의미합니다. 따라서 대부분의 경우에는 다른 정렬 알고리즘을 사용하는 것이 효율적일 수 있습니다.

Java에서의 버블 정렬 사용

다음은 자바에서의 버블 정렬 구현 코드입니다:

void bubbleSort(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1]) {
                // swap arr[j+1] and arr[j]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
}

이 코드는 배열의 길이를 구한 후, 두 번의 for문을 통해 배열을 반복하면서 인접한 두 원소를 비교합니다. 앞의 원소가 뒤의 원소보다 크다면, 두 원소의 위치를 바꿔주는 과정을 반복합니다.

이 과정을 통해 가장 큰 원소가 배열의 가장 오른쪽으로 이동하게 되고, 이를 반복하여 전체 배열이 정렬되는 것입니다. 이 때, 두 번째 for문에서 n-i-1을 하는 이유는, 각 반복마다 가장 큰 원소가 오른쪽으로 이동하게 되어, 그 이후에는 더 이상 비교하지 않아도 되기 때문입니다.

이렇게 버블 정렬은 간단하면서도 직관적인 알고리즘으로, 이해하고 구현하기 쉽다는 장점이 있습니다. 그러나 앞서 언급했듯이, 시간 복잡도가 O(n^2)이므로 데이터의 크기가 큰 경우에는 다른 정렬 알고리즘을 사용하는 것이 좋습니다.