[알고리즘] 버블정렬(bubble sort)이란? | c언어 버블정렬 구현

버블 정렬(Bubble Sort)

버블 정렬은 현재 원소와 다음 원소를 비교하여 조건에 맞으면 교환하는 식의 정렬이다. 원소가 거품처럼 올라오는 듯해 버블 정렬이라는 이름이 붙었다.

 

위와 같은 배열을 오름차순으로 버블 정렬한다고 하자. 

 

처음 7과 5를 비교해 7이 더 크므로 위치를 바꾼다. 이후 배열의 끝까지 비교해서 값이 더 크다면 위치를 바꿔준다.

 

다시 5와 1을 비교해 5가 더 크므로 위치를 바꿔준다. 이번엔 정렬이 끝난 7 전까지만 해당 과정을 반복 해준다.

다시 1과 4를 비교해 1이 더 작으므로 위치를 바꾸지 않는다. 이후 4와 3을 비교했을 때 4가 더크므로 위치를 바꿔준다.

1과 3을 비교해 1이 더 작으므로 위치를 바꾸지 않는다. 이렇게 하면 버블 정렬이 완료된다.

버블정렬의 특징

  • 버블 정렬은 하나의 배열에서 값을 바꾸는 식으로 동작하므로 공간 복잡도는 O(1)이다. 선택정렬과 마찬가지로 swap 할 때 필요한 임시변수 정도의 추가공간만 있으면 되므로 in-place 정렬이다.
  • (n-1), (n-2) ... 1번 의 탐색이 필요하므로 시간복잡도는 O(n^2)이다.
  • 버블 정렬은 중복된 키 값의 순서가 정렬 후에도 유지되므로 stable 정렬이다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#define LEN 5
 
void bubbleSort(int* arr){
    int i,j, temp;
    for(i=0; i < LEN; i++){
        for(j=0; j<LEN-i-1; j++){
            if(arr[j] > arr[j+1]){    // swap
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1= temp;
            }
        }
    }
}
 
int main(){
    int arr[LEN] = {7,5,1,4,3};
    int i;
    printf("정렬 전 : ");
    for(i=0; i<5; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    bubbleSort(arr);
    printf("정렬 후 : ");
    for(i=0; i<5; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");    
    
    return 0
}
cs
 

실행결과

 

 


 

반응형

댓글

Designed by JB FACTORY