<개인공부>/[Algorithm]

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

사용자 BlockDMask 2017. 7. 31. 08:30
반응형


안녕하세요, 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) 에 대해서 포스팅 하겠습니다.

반응형
1 ··· 3 4 5 6 7 8