버블정렬 Bubble Sort

정의

오름차순으로 정렬하는 기초적인 알고리즘 중 하나

기법

무차별 대입 Brute Force

알고리즘 순서

1. 두 숫자(첫번째와 두번째)를 비교하며 순회한다
2. 두 숫자를 비교하여, 작은수를 왼쪽, 큰수를 오른쪽으로 이동시킨다.
3. 첫번째 선회를 하면, 맨 오른쪽에 가장 큰 수가 위치하게 된다
4. 마찬가지로 하나씩 줄여가며 순회하면 완성

자바 코드

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

평균 시간 복잡도 Avg. time complexity

$O(n^2)$

최악 시간 복잡도 Worst time complexity

$O(n^2)$

공간 복잡도 space complexity

$O(1)$

안정성 stability

yes

계산법

순회 횟수

$n-1$

가장 많이 방문한 요소 수

$n-1$ (첫번째 요소)

가장 적게 방문한 요소 수

$1$ (마지막 요소)

평균적으로 방문한 요소 수

(가장 많이 방문한 요소 수+가장 적게 방문한 요소)/2 $= \frac{(n-1+1)}{2} = \frac{n}{2}$

다항식 시간

순회 횟수*평균적으로 방문한 요소 수 $=(n-1)\cdot \frac{n}{2}$

시간 복잡도

$O(다항식 시간)=O((n-1)\cdot \frac{n}{2})=O((\frac{n^2}{2}-\frac{n}{2}))=O(n^2)$