[C] <자료구조> 버블정렬 알고리즘 bubble sort 시간 복잡도

버블 정렬

버블 정렬은 인접한 두 원소를 비교하여 정렬하는 방법이다.

시간 복잡도는 평균 O(n²)로 느리고 비효율적이지만 코드가 단순하기 때문에 자주 사용된다.

시간 복잡도의 최상은 O(n), 최악은 O(n²)을 기록한다.

다음 영상은 버블 정렬 동작 방식이다.

#include <stdio.h>
void bubble_sort(int arr[], int len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}
void main() {
    int arr[] = { 9,2,6,5,8,3,1 };
    int len = sizeof(arr) / sizeof(int); // 배열 길이
    bubble_sort(arr, len);
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
}