거품정렬

 

 

1. 배열을 순회하면서 인접한 두 요소를 비교한다.

2. 두 요소의 순서가 잘못되었으면 교환한다.

3. 배열 끝까지 한 번 순회하면 가장 큰 요소가 배열의 끝으로 이동한다.

4. 위 과정을 반복하면서 정렬되지 않은 부분을 점차 줄여나간다.

 

특징

• 시간 복잡도:
  • 최악
    • O(n²) (배열이 역순으로 정렬된 경우)
  • 평균
    • O(n²)
    • (n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2
  • 최선
    • O(n) (이미 정렬된 경우)
• 공간 복잡도
  •  O(1) (추가 메모리가 필요하지 않음)
    • 주어진 배열 안에서 교환(swap)을 통해 정렬이 수행
• 단순성
  • 구현이 쉽다.
  • 효율성이 낮아 실무에서는 잘 사용하지 않는다.

 

장점

• 구현이 매우 간단하다.
• 작은 데이터셋에서는 작동이 가능하다.
• 추가 메모리가 필요하지 않다.

 

단점

• 시간 복잡도가 매우 높다.
• 큰 데이터셋에서는 비효율적이다.
• 이미 정렬된 배열에서도 기본적인 구현은 모든 비교를 수행한다

 

JAVA

import java.util.Arrays;

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n; i++) {
            swapped = false;
            // 마지막 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;
                    swapped = true;
                }
            }
            // 교환이 없으면 이미 정렬된 상태
            if (!swapped) break;
        }
    }

    public static void main(String[] args) {
        int[] array = {5, 3, 8, 6, 2};
        System.out.println("정렬 전: " + Arrays.toString(array));
        bubbleSort(array);
        System.out.println("정렬 후: " + Arrays.toString(array));
    }
}

 

 

 

Python

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        # 마지막 i개의 요소는 이미 정렬됨
        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


array = [5, 3, 8, 6, 2]
print("정렬 전:", array)
sorted_array = bubble_sort(array)
print("정렬 후:", sorted_array)