[알고리즘] 버블정렬

버블정렬(Bubble Sort)이란 ?

버블정렬은 서로 인접한 두 수를 검사하여 정렬하는 알고리즘입니다.

 

9 8 7 3 2 5 4 1 6 이런 배열이 있다면

 

8 9 7 3 2 5 4 1 6

8 7 9 3 2 5 4 1 6

8 7 3 9 2 5 4 1 6

...

8 7 3 2 5 4 1 9 6

8 7 3 2 5 4 1 6 9 이렇게 가장 큰 수가 맨 뒤로 가게 됩니다.

 

그럼 그 다음부터는 8번째 원소 까지만 정렬을 해줍니다.

 

    public int[] solution(int n, int[] arr) {

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

        return arr;
    }

길이가 n인 배열 arr을 입력 받았을 때 버블정렬 하는 코드입니다.

 

버블정렬의 시간복잡도는 선택정렬과 같은 O(N^2)입니다.

하지만 버블정렬은 자리바꿈이 계속해서 일어나기 때문에

대표적인 정렬 알고리즘 중 가장 느립니다.