[정렬] 버블 정렬 Bubble Sort

버블 정렬 Bubble Sort

 

버블 정렬이란?

버블 정렬은 배열의 인접 요소(adjacent element)를 비교하여 교환하는 모양이 마치 거품이 움직이는 모양이라고 해서 붙여진 이름이다.

 

인접한 두 개의 배열 요소를 비교 및 교환하여 최댓값을 제일 뒤로 보내는 전략이다.

구현은 간단하나 그에 비해 속도는 느린 편이다.

 

 

정렬 예시

 

 

Code / C언어 기반

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define SIZE 10
 
int arr[SIZE];
 
//Print Array
void printArr() {
    printf(" [ ");
    for (int i = 0; i < SIZE; i++)
        printf("%2d ", arr[i]);
    printf("]\n\n");
}
 
 
int main() {
    srand(time(NULL));
 
    for (int i = 0; i < SIZE; i++)
        arr[i] = rand() % 100;
 
    //Origin
    printf(" Before\n");
    printArr();
 
    //Bubble Sort
    for (int i = 0; i < SIZE - 1; i++) {
        for (int j = 1; j < SIZE - i; j++) {
            if (arr[j - 1] > arr[j]) {
                int tmp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
 
    //Result
    printf(" After\n");
    printArr();
 
    return 0;
}

 

[출력 결과]

 

 

시간 복잡도

[ 버블 정렬 시간복잡도 ]