거품 정렬

개요

너비가 2인 Window를 (n-1)번 정도 움직이며 Window의 내에서 Swap하며 정렬하는 방법.

---

복잡도

	최악	평균	최소
Big O 표기법	O(n^2)	O(n^2)	O(n^2)

---

알고리즘 절차

 

1. 인덱스 0부터 인덱스 n-2까지 움직이는 크기가 2인 Window를 운용한다. 이 때, 윈도우를 움직일 때마다 크기가 정렬되어 있지 않다면 Swap하기.
2. 1번의 결과로 n-1에는 최대값이 위치하게 되고 다시 인덱스 0부터 인덱스 n-3까지 움직이는 Window를 운용한다.
3. 이 과정을 모든 요소가 정렬될 때까지 진행한다.

---

자바 코드

class Bubble {
    public static void main(String[] args) {
        int[] testCase1 = {1, 26, 9, 67,653,452,2,3,46,87,356543};

        bubbleSort(testCase1);

        for (int item : testCase1) {
            System.out.println(item);
        }
    }
    
    public static void bubbleSort(int[] arr) {
        for(int i=arr.length-1; i>=0; i--) {
            for(int j=0; j<i; j++) {
                if(!(arr[j] <= arr[j+1])) {
                    swap(arr,j,j+1);
                }
            }
        }
    }
    
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}