Bubble Sort(거품 정렬, 버블 소트)

Bubble sort 란?

버블 소트(Bubble Sort)는 가장 간단하면서도 직관적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 인접한 두 원소를 비교하여 잘못된 순서(예: 오름차순 정렬에서 더 큰 수가 왼쪽에 위치하는 경우)가 발견될 때마다 이를 교환합니다. 이 과정을 모든 원소가 올바른 순서로 정렬될 때까지 반복합니다. 이 알고리즘의 이름은 더 큰 원소들이 마치 '거품'처럼 배열의 끝으로 '떠오르는' 모습에서 유래했습니다.

 

Bubble sort 사이클

버블 소트의 한 사이클은 배열의 첫 번째 원소부터 시작해 마지막 원소까지 진행됩니다. 각 단계에서, 현재 원소와 그 다음 원소를 비교하여 현재 원소가 다음 원소보다 크면 두 원소의 위치를 바꿉니다. 이 과정은 배열의 끝에 도달할 때까지 반복되며, 한 사이클이 완료되면 가장 큰 원소가 배열의 맨 끝으로 '떠오릅니다'. 이를 통해, 각 사이클마다 정렬되지 않은 부분의 가장 큰 원소가 올바른 위치로 이동하게 됩니다.

 

Bubble sort 시간복잡도

• 시간 복잡도
  • 최선의 경우(Best Case): 𝑂(𝑛) - 이미 정렬된 배열을 정렬할 때, 첫 번째 사이클에서 어떤 교환이 일어나지 않으면 정렬이 완료된 것으로 판단할 수 있습니다.
  • 최악의 경우(Worst Case): 𝑂(𝑛2) - 역순으로 정렬된 배열(예: 내림차순으로 정렬된 배열을 오름차순으로 재정렬해야 하는 경우)을 정렬할 때 각 원소가 정확한 위치로 이동하기 위해 최대한 많은 비교와 교환이 필요합니다.
• 공간 복잡도: 𝑂(1) - 버블 소트는 추가적인 메모리 공간을 필요로 하지 않으멀로, 공간 복잡도는 상수입니다. 이는 정렬을 위해 원본 배열 외에 추가적인 저장 공간이 필요하지 않다는 것을 의미합니다.

Bubble sort 장단점

장점

1. 이해하기 쉽고 구현하기 간단함: 버블 소트는 알고리즘의 원리가 매우 단순하므로 초보자도 쉽게 이해하고 구현할 수 있습니다.
2. 추가 메모리 필요 없음: 인플레이스(in-place) 정렬 알고리즘이므로, 추가적인 메모리가 필요 없습니다. 즉, 공간 복잡도가 𝑂(1)입니다.
3. 안정적인 정렬 알고리즘: 동일한 값을 가진 요소들의 상대적인 순서가 정렬 과정에서 바뀌지 않습니다.
4. 정렬이 거의 완료된 배열에 효율적: 이미 정렬된 배열 또는 거의 정렬된 배열에 대해서는 빠르게 작동할 수 있으며, 이 경우 최선의 시간 복잡도인 𝑂(𝑛)에 가까워집니다.
5. 안정 정렬(stable sort) 알고리즘: 안정 정렬이란, 동일한 값을 가진 요소들 사이의 상대적인 순서가 정렬 과정에서 유지되는 정렬 방식을 말합니다. 버블 소트에서는 인접한 요소들을 비교하고 필요할 경우에만 위치를 교환합니다. 이때, 동일한 값을 가진 요소들의 경우 교환이 이루어지지 않기 때문에, 그들 사이의 초기 순서가 보존됩니다. 이러한 특성 덕분에 버블 소트는 안정적인 정렬 알고리즘으로 분류됩니다.

 

단점

1. 비효율적인 시간 복잡도: 버블 소트의 평균적인 시간 복잡도는 𝑂(𝑛2)입니다. 배열의 크기가 커질수록 성능이 급격히 떨어지므로, 큰 데이터 세트에는 부적합합니다.
2. 많은 교환 연산: 인접한 요소를 반복적으로 교환해야 하므로, 다른 𝑂(𝑛2) 정렬 알고리즘(예: 삽입 정렬)보다 실제 성능이 더 나쁠 수 있습니다.
3. 비효율적인 비교: 정렬 과정에서 배열의 끝에 이미 정렬된 요소에 대해서도 비교를 계속 수행합니다.

Bubble sort 코드

golang

package main

import "fmt"

func bubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

func main() {
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    bubbleSort(arr)
    fmt.Println("Sorted array:", arr)
}

 

java

public class BubbleSort {
    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]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

    public static void main(String args[]) {
        BubbleSort bs = new BubbleSort();
        int arr[] = {64, 34, 25, 12, 22, 11, 90};
        bs.bubbleSort(arr);
        for (int i=0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

 

python

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

# 예제 배열
example_array = [64, 34, 25, 12, 22, 11, 90]

# 버블 소트 실행
sorted_array = bubble_sort(example_array)
print("Sorted array:", sorted_array)

sort