JAVA 버블 정렬 (Bubble Sort)

버블 정렬(bubble sort)은 서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식이다.

public class Study {
 
    public static void main(String[] args) {
        int arr[] = {10, 50, 20, 33, 40};
 
        for(int i=0; i<arr.length-1; i++)
            for(int j=0; j<arr.length-1-i; j++)
                if(arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
        for(int i=0; i<arr.length; i++)
            System.out.print(arr[i] + " ");
    }
}

여기서 6 ~ 12 번째 줄이 정렬 알고리즘이다.

첫 번째 반복문 조건값에서 -1을 해준 이유는 사이클 마지막 때 정렬이 이미 되어있다.

근데 여기서 -1을 안 해줬으면 반복문이 한 사이클 더 돌게 된다.

두 번째 반복문 조건값에서 -1-i를 해줬는데 해준 이유는

인덱스 오류가 나기 때문에 -i를 해줬다.

그리고 if 문을 통해 값을 바꾸게 된다.

for(int i=0; i<arr.length-1; i++)
    for(int j=0; j<arr.length-1-i; j++)
        if(arr[j] > arr[j+1]) {
            int temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
            }

이것은 내림차순으로 정렬을 한 것이다. 위의 소스코드랑 뭐가 다른지 분석을 해보자.

이 정렬 알고리즘을 시간 복잡도로 나타내면 O(n^2)로 나타낸다. 반복문 두 번이 도니 n^2이다.

public class Study {
 
    public static void main(String[] args) {
        int arr[] = { 3,4,5,6,7 };
        boolean flag = true;
     
        for (int i = 0; i>0 && flag; i--) {
            for (int j = 0; j<i; j++) {
                flag = false;
                    if (arr[j] > arr[j + 1]) {
                        int temp = arr[j];
                            arr[j] = arr[j + 1];
                            arr[j + 1] = temp;
                            flag = true;
                    }
            }
        }
        for(int i=0; i<arr.length; i++)
            System.out.print(arr[i] + " ");
    }
}

이 알고리즘은 조금 더 향상된 버블 정렬이다.

코드 상으로 보면 어디 가 향상된지는 모르겠다.

다만 알고리즘 적으로 보면 이미 정렬된 데이터가 있다.

이 알고리즘은 정렬이 필요 없으면 프로그램을 끝내게 된다.

일반 버블 정렬은 이미 정렬이 되어있어도 계속 반복문은 돌아간다.

이 알고리즘은 시간 복잡도로 나타내면 최악의 경우 O(n^2)이고 최선의 경우는 O(n)이다.

최악의 경우 일반 버블 정렬과 같으니 이 알고리즘을 사용하는 게 좋다.