[C] 버블 정렬 예제 정리

[C] 버블 정렬 예제 정리

버블 정렬은 인접한 배열의 요소를 비교 교환하여 전체적으로는 대충 정렬을 하면서 최대값을 배열의 제일 뒤로 보내는 것을 반복한다.

버블 정렬은 비교 교환하며 최대 값을 제일 뒤로 보내기 때문에 정렬의 전과정을 하지 않아도 이미 정렬되어 있는 경우가 많다. 또한 안정성이 있다.

#include <stdio.h>      void bubble_sort(int a[], int n){     int i, j, t;     for (i = 0; i < n - 1; i++){         for (j = 1; j < n - i; j++){             if (a[j - 1] > a[j]){                 t = a[j - 1];                 a[j - 1] = a[j];                 a[t] = t;             }         }     } }

버블 정렬의 최선의 경우는 주어진 배열이 이미 정렬된 배열일 경우이다.

이 경우 버블 정렬은 N*(N-1)/2 번의 비교를 하게 되며 교환은 없다.

최악의 경우는 역순 배열일 경우이다.

역순 배열일 경우 비교와 교환의 횟수는 N*(N-1)/2번이다.

버블 정렬은 이중 루프를 가지고 있으므로 O() 의 성능을 가진다.

버블 정렬은 모든 경우에 있어 고르게 속도가 느리다.

* 버블 정렬의 개선

버블 정렬은 최초 루프 탐색 동안 교환이 한번도 일어나지 않았으면, 정렬이 완료된 상태이다.

따라서 더이상 정렬을 진행할 필요가 없다.

아래와 같이 개선하여, 이미 정렬이 완료된 배열에 대해 탐색을 최소화 할 수 있다. 

#include <stdio.h> void gen_bubble_sort(void *base, size_t nelem, size_t width,     int(*fcmp)(const void*, const void*)){          int i, j, s;     void *t;     t = malloc(width);     for (i = 0; i < nelem; i++){         s = 1;         for (j = 1; j < nelem - i; j++){             if (fcmp((char*)base + (j - 1)*width, (char*)base + j*width) > 0){                 memcpy(t, (char*)base + (j - 1)*width, width);                 memcpy((char*)base + (j - 1)*width, (char*)base + j*width, width);                 memcpy((char*)base + j*width, t, width);                 s = 0;             }         }         if (s == 1) break;     } }

* 일반화된 함수 작성

버블 정렬을 int에 대한 배열 뿐만 아니라 다양한 타입에 적용할 수 있도록 아래와 같이 변경할 수 있다.

#include <stdio.h> #include <malloc.h> #include <memory.h> #include <string.h> void gen_bubble_sort(void *base, size_t nelem, size_t width,     int(*fcmp)(const void*, const void*)){          int i, j, s;     void *t;     t = malloc(width);     for (i = 0; i < nelem; i++){         s = 1;         for (j = 1; j < nelem - i; j++){             if (fcmp((char*)base + (j - 1)*width, (char*)base + j*width) > 0){                 memcpy(t, (char*)base + (j - 1)*width, width);                 memcpy((char*)base + (j - 1)*width, (char*)base + j*width, width);                 memcpy((char*)base + j*width, t, width);                 s = 0;             }         }         if (s == 1) break;     } }

출처: https://hyeonstorage.tistory.com/358?category=622873 [개발이 하고 싶어요]