[Algorithm] Generic Swap and Sort
Generic Swap
Swap 함수는 어디서든 많이 쓰는 함수 중 하나다. 그런데 type에 무관한 swap 함수가 필요할 수 있기 때문에 타입에 무관함 swap 함수를 소개한다.
(C++에선 함수 overloading이 가능해서 동일한 함수 이름이여도 타입이 다르면 다르게 호출 될 수 있음)
#include <stdio.h>
void swap (char *a, char *b, int size) {
char t;
int i;
for(i=0; i<size; i++) {
t = a[i];
a[i] = b[i];
b[i] = t;
}
}
int main() {
int a=3, b=4;
double ad = 3., bd = 4.;
swap((char *)&a, (char *)&b, sizeof(a));
swap((char *)&ad, (char *)&bd, sizeof(ad));
printf("a = %d, b = %d\n", a, b);
printf("ad = %lf, bb = %lf\n", ad, bd);
return 0;
}
만약 C에서 타입에 무관하게 swap 함수를 구현한다고 하면 위 코드처럼 1 byte씩 swap을 진행해야 한다. 그러나 매번 user가 타입 캐스팅 (char *)를 진행해줘야 하는 번거로움이 존재한다. 따라서 우리는 이 때 void *를 사용하면 된다.
#include <stdio.h>
void swap (void *a, void *b, int size) {
char t;
int i;
char *pa = (char *)a;
char *pb = (char *)b;
for(i=0; i<size; i++) {
t = pa[i];
pa[i] = pb[i];
pb[i] = t;
}
}
int main() {
int a=3, b=4;
double ad = 3., bd = 4.;
swap(&a, &b, sizeof(a));
swap(&ad, &bd, sizeof(ad));
printf("a = %d, b = %d\n", a, b);
printf("ad = %lf, bb = %lf\n", ad, bd);
return 0;
}
위 코드는 user가 swap 함수를 호출 할 때 더 이상 type casting이 없어도 문제없이 동작하는 것을 볼 수 있다. 실제 kernel에서도 위와 같은 generic swap 코드가 존재한다.
void generic_swap(void *a, void *b, int size)
{
char t;
do {
t = *(char *)a;
*(char *)a++ = *(char *)b;
*(char *)b++ = t;
} while (--size > 0);
}
Generic Sort
일반적으로 sort에 사용하는 알고리즘인 bubble sort는 아래와 같다.
void bubble_sort(int *a, int n) {
for (int i=0; i<n-1; i++)
for (int j=0; j<n-1-i; j++)
if (a[j] > a[j+1])
generic_swap(a+j, a+j+1, sizeof(a[0]));
}
Swap과 마찬가지로 void pointer를 사용하면 아래와 같이 될 것이다.
#include <stdio.h>
void generic_swap(void *a, void *b, int size)
{
char t;
do {
t = *(char *)a;
*(char *)a++ = *(char *)b;
*(char *)b++ = t;
} while (--size > 0);
}
void bubble_sort(void *a, int n, int size) {
for (int i=0; i<n-1; i++)
for (int j=0; j<n-1-i; j++)
if (*((char *)a+j*size) > *((char *)a+(j+1)*size))
generic_swap((char *)a+j*size, (char *)a+(j+1)*size, size);
}
int main()
{
int a[] = { 5, 2, 3, 0, 7, 6, 1, 4};
int i;
for(i=0; i<(sizeof(a)/4); i++ )
printf("%4d", a[i] );
printf("\n");
bubble_sort(a, sizeof(a) / sizeof(a[0]), sizeof(a[0]));
for(i=0; i<(sizeof(a)/4); i++ )
printf("%4d", a[i] );
printf("\n");
return 0;
}
5 2 3 0 7 6 1 4 0 1 2 3 4 5 6 7
그런데 만약 숫자를 좀 더 키워서 하면 결과가 달라질 것이다.int a[] = { 500, 200, 300, 0, 700, 600, 100, 400};
500 200 300 0 700 600 100 400 400 700 200 500 0 300 600 100
문제가 되는 부분은 double_sort 함수에서 if (*((char *)a+j*size) > *((char )a+(j+1)size)) 가 찍는 코드는 1 byte만 나오기 때문에 문제가 되는 것이다. 따라서 추가로 (int *)로 다시 캐스팅을 하면 다시 type에 무관한 함수가 되지 않게 된다.
결론은 값의 비교가 필요한 알고리즘은 일반화를 할 수 없기 때문에, 비교 함수는 유저가 작성해서 넘겨주는 방식을 채택한다.
void bubble_sort(void *a, int n, int size, int (*cmp)(const void*, const void*)) {
for (int i=0; i<n-1; i++)
for (int j=0; j<n-1-i; j++)
if (cmp((char *)a+j*size, (char *)a+(j+1)*size))
generic_swap((char *)a+j*size, (char *)a+(j+1)*size, size);
}
위 코드를 보면 함수 포인터를 4번째 함수 인자로 넘겨준다. 해당 함수는 첫 번째 인자가 두 번째 인자보다 크면 true를, 그렇지 않으면 false를 return하는 함수다.
실제 Linux Kernel에서도 위 함수 구조와 동일하게 설계되어있다.
#include <stdio.h>
#include <stdlib.h>
typedef unsigned int u32;
int int_cmp(const void* a, const void *b) {
return (*int *)a - *(int *)b);
}
void u32_swap(void *a, void *b, int size)
{
u32 t = *(u32 *)a;
*(u32 *)a = *(u32 *)b;
*(u32 *)b = t;
}
void generic_swap(void *a, void *b, int size)
{
char t;
do {
t = *(char *)a;
*(char *)a++ = *(char *)b;
*(char *)b++ = t;
} while (--size > 0);
}
void sort(void *base, size_t num, size_t size,
int (*cmp_func)(const void *, const void *),
void (*swap_func)(void *, void *, int size))
{
/* pre-scale counters for performance */
int i = (num/2 - 1) * size, n = num * size, c, r;
if (!swap_func)
swap_func = (size == 4 ? u32_swap : generic_swap);
/* heapify */
for ( ; i >= 0; i -= size) {
for (r = i; r * 2 + size < n; r = c) {
c = r * 2 + size;
if (c < n - size &&
cmp_func(base + c, base + c + size) < 0)
c += size;
if (cmp_func(base + r, base + c) >= 0)
break;
swap_func(base + r, base + c, size);
}
}
/* sort */
for (i = n - size; i > 0; i -= size) {
swap_func(base, base + i, size);
for (r = 0; r * 2 + size < i; r = c) {
c = r * 2 + size;
if (c < i - size &&
cmp_func(base + c, base + c + size) < 0)
c += size;
if (cmp_func(base + r, base + c) >= 0)
break;
swap_func(base + r, base + c, size);
}
}
}
내부에 사용하는 sort 알고리즘은 heap sort로 속도는 제일 빠르지 않지만 메모리를 가장 적게 사용하는 알고리즘을 채택해서 쓰고 있다.