버블 정렬(bubble sort) 란?

버블 정렬의 원리

버블 정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 이러한 리스트의 비교-교환 과정이 한번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다. 이러한 비교-교환 과정은 전체 숫자가 전부 정렬될 때까지 계속한다.

 

 

 

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

 

 

바로 자바로 구현해보자.

public class BubbleSort {
    public static void main(String[] args) {
        int[] list = {7, 4, 5, 1, 3};
        int tmp = 0;
        // 버블 정렬

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

        for (int l : list) {
            System.out.print(l + " ");
        }
    }
}

 

버블 정렬의 복잡도 분석

1. 비교횟수

1 + 2 + 3 ... + n-1 = n(n-1)/2 = O(n*n) 

 

최악의 이동 횟수는 입력 자료가 역순으로 정렬되어 있는 경우에 발생하고 그 횟수는 비교 연산의 횟수에 3을 곱한 값이다. 왜냐하면 Swap을 통해서 3개의 이동을 포함하고 있기 때문이다. 최선의 경우는 입력 자료가 이미 정렬이 되어 있는 경우이다. 이런 경우에는 자료 이동이 한 번도 발생하지 않는다. 

 

 

 

버블 정렬의 문제점 

• 순서에 맞지 않은 요소를 인접한 요소와 교환한다
• 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환해야함
• 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어남 
• 일반적으로 교환 작업이 이동 작업보다 더 복잡하기 때문에 버블정렬은 단순함에도 불구하고 잘 쓰이지 않음

 

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

 

버블정렬은 구현하기가 상당히 쉽지만, 성능에서 너무 좋지 않기 때문에 쓰지 않는다고 한다. 

위의 경우만 봐도 시간이 엄청나게 차이난다.