[알고리즘] 버블 정렬 (Bubble Sort) - 자바 Java

[ 개념 ] 

인접한 두 개의 원소를 비교하며 자리를 계속 교환하여 정렬하는 알고리즘
- 비교 정렬, 제자리 정렬, 안정 정렬에 속함

📍 안정 정렬 VS 불안정 정렬
- 안정 정렬: 중복된 값을 입력 순서와 동일하게 정렬하는 정렬 알고리즘(버블정렬, 삽입정렬, 병합정렬 등)
- 불안정 정렬: 중복된 값이 입력 순서와 동일하지 않게 정렬되는 정렬 알고리즘(퀵정렬, 선택정렬, 계수정렬 등)

[ 과정 설명 (오름차순) ] 

- 첫 번째 원소부터 인접한 원소끼리 값을 비교하며 오른쪽이 큰 숫자일 수 있도록 계속 자리를 교환하며 맨 마지막 자리까지 이동
- 한 단계가 끝나면 가장 큰 원소가 맨 뒤로 이동하므로, 다음 단계부터는 가장 뒤에 있는 요소는 정렬에서 제외
- 다시 첫 번째 원소부터 값을 비교하며 이동하며 정렬을 1회 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어남

[ 코드 예시 (오름차순) - 자바 Java ]

public class BubbleSort {

  public static void main(String[] args) {
    int[] arr = { 5, 1, 7, 2, 4 };
    bubbleSort(arr);
  }
  
  // 외부에서 접근 가능한 메소드 선언해주기. (메소드 오버로딩)
  public static void bubbleSort(int[] arr) {
    bubbleSort(arr, arr.length);
  }

  // 외부에서 메소드 변경할 수 없도록 private으로 바꿔주기.
  // 배열을 돌며 앞의 원소와 뒤의 원소 비교.
  private static void bubbleSort(int[] arr, int arrSize) {

    for (int i = 0; i < arrSize1; i++) {
      for (int j = 1; j < arrSize - i; j++) {
        if (arr[j-1] > arr[j]) {
          swap(arr, j-1, j);
        }
      }
    }
  }

  // 원소들의 자리를 바꿔주는 메소드 선언.
  private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

}

[ 시간 복잡도 ] 

- 외부 루프를 N-1번 도는 동안, N-1, N-2, N-3, ..., 1번 인접한 원소들을 비교
- T(n) = (n-1) + (n-2) + (n-3) + ... + 1 = (n-1) * n / 2
- O(n) = n^2