[Algorithm] 버블 정렬 Bubble Sort

정의

버블 정렬은 선택 정렬과 유사한 알고리즘으로 인접한 두 원소를 비교하고, 조건(오름차순 또는 내림차순)과 상이하면 교환하는 알고리즘
 

과정

1. 첫 원소와 다음 원소를 비교하여 N-1번 원소와 마지막 원소를 비교하여 조건에 맞지 않으면 교환
2. 가장 크거나 작은 원소가 맨 뒤로 이동하므로 다음 차수에선 맨 끝 원소는 정렬에서 제외, 차수가 늘어날 수 록 원소가 하나씩 제외
 

코드 및 풀이

public class Main {
  public static void main(String[] args) {
    int[] arr = { 64, 32, 15, 23, 33, 10 };

    bubbleSort(arr);

    System.out.println("Sorted array:");

    for (int num : arr) {
      System.out.println(num + " ");
    }
  }

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

      if (!swapped) {
        break;
      }
    }
  }
}

 

• boolean swapped을 통해 교환 발생 여부를 파악
  • 내부 for 문에서 더 이상의 교환이 발생하지 않았으면, 더 이상 반복할 필요가 없으므로 외부 for문을 중단한다.

 

시간복잡도

• 최선의 경우
  • 배열이 이미 정렬된 경우기에 O(N)
• 평균 및 최악의 경우
  • 외부 for문에서 n-1번 수행
  • 내부 for문에서 n-1, n-2 ~ 1번 실행
  • 따라서 n-1 + n-2 + ... + 1 = N(N-1) / 2 = O(N^2)

공간복잡도

• 추가적인 공간을 요구하지 않는 정렬
  
  • 입력받은 배열에서 정렬이 수행된다.
• 그러므로 O(1)

장점

1. 구현이 간단하고 이해하기 쉽다.
2. 추가 메모리 공간을 요구하지 않는다.
3. 이미 정렬된 알고리즘에서는 최적화를 통해 성능 향상을 시킬 수 있다.

단점

1. 평균 및 최악의 경우 시간 복잡도가 O(N^2) 이기에 대규모 데이터에 대해 비효율적이다.
2. 또한, 최악의 경우 성능이 좋지 않다.
3. 삽입 정렬과 선택 정렬과 같은 알고리즘에 비해 성능이 낮다.