본문 바로가기
<개인공부>/[Algorithm]

버블정렬 (Bubble Sort) 이론과 코드

by 사용자 BlockDMask 2017. 7. 31.
반응형


안녕하세요, BlockDMask 입니다.

오늘은 정렬 알고리즘 중에 버블 소트 (Bubble Sort)에 대해서 알아보도록 하겠습니다.

앞으로 제가 아는 sort들을 포스팅 해볼 예정입니다


버블 정렬 - bubble sort

삽입 정렬 - insertion sort

선택 정렬 - selection sort

퀵 정렬 - quick sort

병합 정렬 - merge sort 

기수 정렬 - radix sort


이 순서대로 정렬 포스트를 진행 해 보도록 하겠습니다.


0. 원리

  • Bubble Sort는 말 그대로 거품처럼 동글동글 하면서 sorting을 합니다. 거품을 연상하시면 쉬울 겁니다.

  • 두 인접한 원소를 비교하는 정렬입니다.

  • 오름차순으로 정렬을 한다고 했을때, 처음 한 바퀴를 돌게 되면 맨 뒤에 있는 인자가 제일 큰 값이 옵니다.

  • 그런식으로 해서 뒤쪽부터 큰 값이 Fix 되면서 정렬을 하게 됩니다.

  • 그림으로 살펴보겠습니다.
    배열 arr 에서 인자가 5개 인 경우를 예로 들어보겠습니다.

    1) 첫번째 사이클입니다. 인자가 5개 이므로 비교는 4번 하게됩니다.
    - 첫번째 사이클 결과로 맨 마지막 값이 Fix 된 것을 볼 수 있습니다. (오름차순 기준으로 제일 큰 값)


    2) 두번째 사이클 입니다. 남아있는 인자의 갯수가 4개이므로 arr[0]~ arr[3]까지 Sort 하면됩니다.


    3) 세번째 사이클는 뒤에서 세번째가 fix가 되고
    4) 네번째 사이클는 뒤에서 네번째가 fix가 되면서. sort를 완료하게 됩니다.

  • 인자가 N 개인 배열일때,
    cycle1일때 N-1 번 비교
    cycle2일때 N-2 번 비교.
    ... ... ...N-3, N-4 . . . . . . . . . .. . . . . .1 이 됩니다.

    1 부터 N-1 까지의 합 만큼 비교가 일어나게됩니다.
    1 ~ N-1 까지의 합은
    N(N-1) / 2 가 됩니다.

  • 위에서 예시를 5개의 인자로 들었기 때문에
    비교 횟수는 4*3 /2 이므로 10 번이 됩니다.


1. 코드

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
35
36
37
38
39
#include <stdio.h>
#define N 5
 
void swap(int * a, int * b){
    int tmp;
    tmp = *a;
    *= *b;
    *= tmp;
}
 
int main(void){
    int i, j;
    int arr[N] = {24135};
 
    printf("Before : ");
    for(i=0; i<N; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
 
 
    //bubble sort.
    for(i = 0; i< N-1 ; i++){
        for(j=0; j< N-1 -i ; j++){
 
            if(arr[j] > arr[j+1]){
                swap(&arr[j], &arr[j+1]);
            }
 
        }
    }
 
 
    printf("After  : ");
    for(i=0; i<N; i++){
        printf("%d ", arr[i]);
    }
    return 0;
}
cs


> 결과



2. 시간 복잡도

  • 시간 복잡도를 구하는 기준은 비교가 제일 많이 일어나는 부분을 통해서 구하게됩니다.
    위에 코드를 보게되면 for문을 두번쓰는 곳 안에 있는 if 문을 기준으로 시간복잡도를 구하면됩니다.

  • 인자의 갯수가 N이라고했을때,
    N-1 + N-2  . . . . . . . . .. . . . .+ 1 이되므로,

    등차수열이므로 식은 N(N-1) / 2 입니다.
    빅오로 계산하게된다면,

      의 시간 복잡도를 가지게 됩니다.

다음시간에는 삽입 정렬(Insertion sort) 에 대해서 포스팅 하겠습니다.

반응형

댓글0