버블 정렬 - 알고리즘

버블 정렬 - Bubble Sort

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

정렬 과정

• 5,3,7,9,1 원소들을 배열에 추가하고 버블 정렬 해보겠습니다
  
  • 1회전 5,3,7,9,1
  • 2회전 3,5,1,7,9
  • 3회전 3,1,5,7,9
  • 4회전 1,3,5,7,9

알고리즘 분석

비교 횟수

 -> 버블 정렬은 한번의 순화를 마칠 때 마다 비교 대상이 하나씩 줄어들기 때문에, 전체 원소의 개수가 n개 라고 할 때, 총 n-1 번 순회하면 정렬이 끝납니다. 위의 예제에서는 총 원소 개수가 5개 이므로, 4+3+2+1 = 10번 비교하게 됩니다. 이를 수식으로 일반화 시키면 다음과 같습니다.

따라서 평균적으로 O(n^2)의 시간복잡도를 가지게 됩니다

 

슈도코드

자바 소스코드:

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

    public static void main(String[] args){
        // 정렬 해야할 배열
        int[] arr = { 4, 1, 5, 6, 2 };
        bubbleSort(arr);
        // 결과 출력
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

 

결과 입출력:

[4,1,5,6,2]

[1,2,4,5,6]