자료구조 - sort (Bubble Sort)

Bubble Sort

정의 : 인접한 두 원소를 비교하여, 큰 수를 계속해서 뒤로 보내 정렬 하는 방식.

• 시간복잡도 O(n^2)
• 대규모 데이터에는 부적합 -> 퀵 정렬, 병합 정렬을 주 사용.

버블 정렬 작동 원리

1. 첫번째 항목부터 마지막 항목까지 순차적으로 이동하면서 인접한 항목을 비교한다.
2. 인접한 두 항목을 비교하면서 왼쪽항목(A[j]) 이 오른쪽 항목 보다(A[j+1]) 크면 위치를 바꾼다.
3. 위의 과정을 반복한다.

package javastudy;

public class bubbleSort {
  public static void bs(int a[]){
    int n = a.length; // 배열 길이.
    boolean swapped;
    int temp;

    for (int i = 0; i < n -1; i++){
      swapped = false; // 스왑 여부 초기화
      for (int j = 0; j < n-i-1; j++){
        if(a[j]>a[j+1]){
          temp = a[j];
          a[j] = a[j+1];
          a[j+1] = temp;
          swapped = true;
        }
      }
      if (!swapped){
        break;
      }
    }
  }

  public static void printArray(int a[]){
    for (int num : a){
      System.out.print(num+" ");
    }
  }

  public static void main(String[] args) {
    int a[] = {8,5,6,2,4};
    System.out.println("정렬전");
    printArray(a);
    System.out.println("정렬후");
    bs(a);
    printArray(a);
  }
}