[C] Bubble Sort 거품 정렬

#include <stdio.h>

void bubble_sort(int userInput[], int count) {
    int temp;
	
    for (int i=0; i< count; i++) { // 2
        for (int j=0; j < count-1; j++) {
        
            if (userInput[j]>userInput[j+1]) { // 1

                temp = userInput[j];
                userInput[j] = userInput[j+1];
                userInput[j+1] = temp;
            }
        }
    }
}

int main(void) {

    int userInput[5];
    int temp;

    for (int i=0; i<5; i++) {
        scanf("%d", &userInput[i]);
    }    

    bubble_sort(userInput, sizeof(userInput)/sizeof(int));

    for (int i=0; i<5; i++) {
        printf("%d ", userInput[i]);
    }
    printf("\n");

    return 0;
}

 

버블 정렬은 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

 

 

1. 앞에서부터 비교해서 큰 수를 뒤에 갖다 박아 놓는다고 생각하면 이해하기 쉽다.

2. 그리고 그걸 n * n-1 번 반복한다.

 

따라서 시간 복잡도는 O(N^2)이다.