버블정렬

버블정렬이란?

인접한 두 수의 크기를 비교해 뒤로 큰 수(오름차순) 또는 작은 수(내림차순)를 뒤로 보내는 정렬 방법입니다.

시간복잡도는?

시간복잡도는 O(N^2)입니다. 모든 수에 대해서 N번만큼 비교를 하기 때문입니다. 

최악의 경우? O(N^2) 

최선의 경우? O(N^2)

보통의 경우? O(N^2)

공간복잡도는?

정렬을 위해 입력받은 배열 이외에는 특별한 저장공간을 할당할 필요가 없습니다. 

그래서 기존의 입력되는 배열인 N개만 필요하므로 O(N)입니다.

어떻게 구현하나?

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

<기준수>

<for문 분석하기! => i = 4, j = 0 ~ 3>

<for문 분석하기! => i = 3, j = 0 ~ 2>

<>

<>