Algorithm - 버블 정렬

버블 정렬

 

배열 정렬 알고리즘으로 거품이 수면 위로 올라오듯이 배열을 정렬한다 해서 버블 정렬이라는 이름이 붙여졌다.

 

 

버블 정렬 구현

 

길이가 n인 배열이 주어졌을때 오름차순으로 정렬하려면

 

1. 인덱스 0번 요소와 바로 오른쪽 요소값을 비교하여 0번 요소가 더 크면 두 값을 교환(swap)

 

2. 인덱스 1, 2, 3, ... n - 2번 요소에 대해 1번 과정 반복하면 배열의 최대값이 마지막에 배치된다.

 

3. 인덱스 1, 2, 3, ..., n - 3번 요소로 위 과정 반복

 

4. 인덱스 1, 2, 3, ..., n - 4번 요소로 위 과정 반복

 

5. 오름차순으로 정렬됨.

 

 

코드

 

public static void main(String[] args) {

    int [] arr = {9, 4, 6, 1, 14, 5};

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

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

 

총 탐색 횟수는 n( n - 1 ) / 2번으로 시간복잡도는 O(n^2), 공간복잡도는 O(n)를 보인다.