버블정렬 알고리즘 (c언어 예제)

버블 정렬(Bubble Sort)

 

버블 정렬이란 서로 인접한 두 수를 비교하여 정렬하는 알고리즘으로, n번째 수와 n+1번째 수를 비교하여 n번째 수가 더 클 경우 n+1번째 수와 교환하는 방법이다.

뒤부터 정렬되는 알고리즘으로, 다른 알고리즘들과 달리 flag를 사용하여 이미 정렬을 완료하였다면 멈출 수 있다.

시간 복잡도는 O(n²)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.

 

 

 

수는 총 5개이므로 4번을 돌아야 하지만, flag를 사용하여 3회전 만에 정렬을 끝낼 수 있다.

처음 주어진 수에서 첫 번째와 두 번째, 두 번째와 세 번째, 세 번째와 네 번째, 네 번째와 다섯 번째 수를 비교하여 맨 뒤부터 정렬되는 것을 볼 수 있다.

 

c언어 예제소스

 

#include <stdio.h>
 
int main() {
 
    int arr[] = { 1,35,22,10, 11 };
    int arrSize = sizeof(arr) / sizeof(int);
    int flag;
    int temp;
 
    //배열 사이즈만큼 반복
    for (int i = 1; i <= arrSize; i++) {
        flag = 0;
        //정렬
        for (int j = 0; j < arrSize - i; j++) {
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                flag = 1;
            }
        }
        //정렬되는 과정 확인
        for (int i = 0; i < arrSize; i++) {
            printf("[%d] ", arr[i]);
        }
        printf("\n");
        //정렬이 완료되었다면 종료
        if (flag == 0) {
            break;
        }
    }
 
    return 0;
}