[정렬 알고리즘] Bubble Sort

Bubble Sort

- 인접한 원소를 하나하나 비교하여 가장 큰 수를 찾아 맨 끝으로 보내면서 정렬하는 알고리즘

- n^2의 시간 복잡도를 갖음. for문을 돌며 (n - 1) * (n - 2) * ... * 2 * 1 번 연산하게 됨

- 시간 복잡도를 생각했을 때 속도가 느려 효율성은 떨어지지만 알고리즘이 단순하여 빠르고 간단하게 구현할 수 있음

 

예제 코드(Java)

public class Test {
    public static void main(String[] args) {
        int [] a = new int[10];

        for(int i = 0; i < a.length; i++) {
            System.out.print(a[i] = (int) (Math.random() * 10));
        }

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