[Algorithm/Java] 버블정렬 (bubble sort)

버블정렬 (bubble sort)

버블정렬은 인접한 두 데이터의 크기를 비교해 두 데이터를 서로 바꿔가며 정렬하는 방법이다.
간단히 구현할 순 있지만, 시간복잡도는 O(n^2)로 다른 정렬 알고리즘보다 속도가 느린 편이다.

---

핵심 이론

정렬되지 않은 정렬의 첫번째 인덱스부터 그 다음 인덱스와 비교하며, 정렬 조건에 따라 자리를 바꿔준다.

1. 루프 범위 설정
2. 인접한 데이터 값을 비교한다.
3. swap조건에 부합하면 swap연산을 수행하고, 부합하지 않으면 그냥 넘어간다.
4. 2번~3번을 반복한다.
5. 전 범위를 반복하면 정렬된다.
   ( 만약 전 범위를 반복하지 않았지만, 만약 하나의 루프에서 swap연산이 한번도 일어나지 않는다면 끝내도된다.)

---

Code

정렬되지 않은 배열 arr이 주어질 때

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for(int i=1;i<n-1;i++) {
        for (int j = 0; j < n-i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}
private static void swap(int[] arr, int i, int j){
    int temp = arr[j];
    arr[j] = arr[i];
    arr[i] = temp;
}