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

안녕하세요, 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. 코드

#include <stdio.h>
#define N 5
 
void swap(int * a, int * b){
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}
 
int main(void){
    int i, j;
    int arr[N] = {2, 4, 1, 3, 5};
 
    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;
}

> 결과

2. 시간 복잡도

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

• 인자의 갯수가 N이라고했을때,
  N-1 + N-2  . . . . . . . . .. . . . .+ 1 이되므로,
  
  등차수열이므로 식은 N(N-1) / 2 입니다.
  빅오로 계산하게된다면,

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

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