알고리즘 - 버블 정렬(Bubble Sort)

버블 정렬

버블 정렬(Bubble Sort) 두 개의 인접한 원소를 비교하여 정렬하는 방식입니다

• 앞에서부터 현재 원소와 바로 다음의 원소를 비교한다.
• 현재 원소가 다음 원소보다 크면 원소를 교환한다.
• 다음 원소로 이동하여 해당 원소와 그 다음원소를 비교한다.

import java.util.Arrays;

public class BubbleSort {
    public static void main(String args[]){
        int[] array = {1,10,5,8,7,6,4,3,2,9};

        bubbleSort(array);

        System.out.println(Arrays.toString(array));
    }

    private static void bubbleSort(int[] array) {
        int temp;
        for(int i=1; i<array.length; i++){  // 배열 크기의 -1만큼 진행
            for(int j=0; j< array.length-i; j++ ){  // 뒤에서부터 정렬되기 때문에 한번씩 줄면서 비교
                if(array[j]>array[j+1]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }
}

시간 복잡도

• n개의 수를 정렬하는 시간은 n-1, n-2, n-3, ...,+2+1번 걸리므로 n-1+n-2+n-3+...+1 = n(n-1)/2
• 버블 정렬의 시간복잡도는 O(n^2)