[알고리즘] 거품 정렬(Bubble Sort)

정의

Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소를 비교하고, 만약 조건에 맞지 않는다면 자리를 교환하여 정렬하는 알고리즘이다.

 

프로세스

1. 1라운드에서는 1번째 원소와 2번째 원소 비교, 2번째 원소와 3번째 원소 비교, 3번째 원소와 4번째 원소 비교,..., (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않으면 서로 교환한다.
2. 1라운드가 끝나면 가장 큰 원소가 마지막 자리로 가게 되고, 2라운드에서는 정렬된 마지막 원소를 제외하고 1과 같은 로직으로 비교하여 정렬한다. 2라운드가 끝나게 되면 마지막에서 2번째 원소도 정렬이 된 상태다. 

 

소스코드

public int[] bubble_sort(int size, int[] arr) {

    // round 횟수: 배열 길이 - 1
    for (int i=1; i<size; i++) {    // i : 라운드 값

        // 각 라운드별 비교횟수: 배열 길이 - 현재 라운드(i)
        for (int j=0; j<size - i; j++) {
            /*
            * 현재 원소가 다음 원소보다 값이 크면
            * 두 원소의 값을 교환한다.
            * */
            if (arr[j] > arr[j+1]) {
                swap(arr, j, j+1);
            }
        }
    }
    return arr;
}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

 

GIF로 이해하기

시간복잡도

비교 연산의 실행 횟수를 계산해보면 n-1, n-2, n-3, ..., 2, 1이고 다 더하면 (n-1)n/2이다. 따라서 버블 정렬의 시간복잡도는 O(n^2)이 된다. 비교 연산의 경우 실제 데이터가 어떻게 들어가있던지(최악, 평균, 최선) 상관없이 항상 비교 연산을 한다. 따라서 최악, 최선, 평균의 경우 모두 시간 복잡도가 O(n^2)이다. 

장점

• 구현이 간단하다.
• 직관적이다.
• 다른 메모리 공간을 필요로하지 않는 제자리 정렬(in-place-sorting)이다.
• 안정 정렬이다.

단점

• 시간 복잡도가 O(n^2)이라서 비효율적인 알고리즘이다.

 

정렬 알고리즘

• 단순(구현이 간단)하지만 비효율적인 정렬 
  • 삽입 정렬, 선택 정렬, 버블정렬
• 복잡하지만 효율적인 정렬
  • 퀵정렬, 힙정렬, 합병정렬, 기수정렬

정렬명(Name)	최선의 경우(Best)	평균의 경우(Average)	최악의 경우(Worst)	수행시간(size:60,000):단위:초
삽입정렬	n	n^2	n^2	7.438
선택정렬	n^2	n^2	n^2	10.842
버블정렬(거품정렬)	n^2(n)	n^2	n^2	22.894
셸정렬	n	n^1.5	n^2	0.056
퀵정렬	nlogn	nlogn	n^2	0.014
힙정렬	nlogn	nlogn	nlogn	0.034
병합정렬	nlogn	nlogn	nlogn	0.026

---

느낀점

구현은 쉽지만 시간복잡도가 O(n^2)으로 상당히 비효율적인 정렬 알고리즘이다. 만약 데이터 크기가 작고 정렬을 구현해야된다면 고려할만 하다.

---

참고

https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html

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