[알고리즘 개념] 정렬 알고리즘 - 버블 정렬 (Bubble Sort)

버블 정렬 (Bubble Sort)

정렬 순서 (오름차순 정렬 기준)

1. 인접한 원소 두 개((arr[0], arr[1]), (arr[1], arr[2]) ~ (arr[n-2], arr[n-1]))를 쌍으로 지어 앞에 위치한 원소가 뒤의 원소보다 크다면 swap한다.
2. 1회전을 끝내게 되면 배열 내의 가장 큰 원소가 가장 마지막에 배치된다. (뒤에서부터 정렬이 완료된다.)
3. 따라서 1~2과정을 정렬되지 않은 원소가 1개가 될때까지 반복한다. 

 

예시

1, 2 회전 후 결과

3,4 회전 후 결과

장점

• 구현이 쉽고 이해하기 쉽다.
• In-place Sorting Algorithm
  • 주어진 배열 내에서 이루어지기 때문에 공간복잡도 O(n)
• 안정 정렬 (Stable Sorting)
  • 중복 값이 입력 순서와 동일하게 정렬 됨

 

단점

•  O(n²)의 시간복잡도
• 정렬을 위해 swap 과정이 많이 일어나게 된다. (계산 시간 상승)
  • 다른 O(n²) 시간 복잡도를 갖는 삽입, 선택 정렬보다 오래 걸리게 된다.

 

시간 복잡도 

• 원소 비교 횟수
  • n-1, n-2, ... ,2, 1 = n(n-1)/2
• swap: 최악의 경우 비교 횟수마다 교환 진행
  • 3 * (n(n-1)/2)
• T(n) =  n(n-1)/2 + (3 * (n(n-1)/2))∈ O(n²) 

 

Code (C/C++)

#include <stdio.h>
#define LENGTH 5

// bubbleSort
void bubbleSort(int* arr){
    // outer loop: 배열 크기 - 1 만큼 반복 (회전 횟수)
    for(int i = 1; i < LENGTH; i++) {
        // inner loop: 각 회전 횟수만큼 뺀 만큼 비교 (회전마다 맨 뒤 공간부터 정렬된다)
        for(int j = 0; j < LENGTH - i; j++) {
            // 이전 원소가 다음 원소보다 큰 경우 swap
            if(arr[j] > arr[j+1]) {
                // swap
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

int main() {
    int arr[LENGTH] = {7,4,2,9,5};
    printf("Before Sorting: ");
    for(int i = 0; i<LENGTH; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    bubbleSort(arr);

    printf("After Sorting: ");
    for(int i = 0; i<LENGTH; i++) {
        printf("%d ", arr[i]);
    }
}

Code (Java)

public class sorting {
    public static void main(String[] args) {
        int[] arr = {7, 4, 2, 9, 5};
        System.out.print("Before Sorting: ");
        printArr(arr);
        bubbleSort(arr);
        System.out.print("After Sorting: ");
        printArr(arr);
    }

    // Print Array
    static void printArr(int[] arr) {
        int l = arr.length;
        for (int i = 0; i < l; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // Bubble sort
    static void bubbleSort(int[] arr) {
        int l = arr.length;
        // outer loop: 배열 크기 - 1 만큼 반복 (회전 횟수)
        for (int i = 1; i < l; i++) {
            // inner loop: 각 회전 횟수만큼 뺀 만큼 비교 (맨 뒤 공간부터 정렬된다)
            for (int j = 0; j < l - i; j++) {
                // 이전 원소가 다음 원소보다 큰 경우 swap
                if (arr[j] > arr[j + 1]) {
                    // swap
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    }
}