Posted on 2010-10-14 00:03
kongkongzi 阅读(209)
评论(0) 编辑 收藏 引用 所属分类:
c programming
/*
* define a generic function bubble_sort which
* calls some sort function using bubble method.
*/
typedef int (*Func)(void *, int);
int bubble_sort(void *arrary[], int len, Func func)
{
return (*func)(arrary, len);
}
int bubble_int(void *array, int len)
{
int *p;
int i, j, temp;
p = (int *)array;
for (i = 1; i < len - 1; i++)
for (j = 0; j < len - i; j++)
if (*(p+j) > *(p+j+1)) {
temp = *(p+j);
*(p+j) = *(p+j+1);
*(p+j+1) = temp;
}
return 0;
}
/*
* from smaller to bigger.
* use bubble method to sort the interger array
* which has 'len' elements.
*/
int bubble_int(void *array[], int len)
{
int *p;
int i, j, temp;
p = (int *)array;
for (i = 1; i < len - 1; i++)
for (j = 0; j < len - i; j++)
if (*(p+j) > *(p+j+1)) {
temp = *(p+j);
*(p+j) = *(p+j+1);
*(p+j+1) = temp;
}
return 0;
}
/*
* sort the array 'a' from the smaller to the bigger.
*/
void insertion_sort(int a[], int len)
{
int i, j, key;
for (j = 1; j < len; j++) {
key = a[j];
i = j - 1;
while (i >= 0 && a[i] > key) {
a[i+1] = a[i];
i--;
}
a[i+1] = key;
}
}
/*
* sort the array 'a' from the smaller to the bigger.
*/
void merge(int a[], int start, int mid, int end)
{
int i, j, k;
int n1 = mid - start + 1;
int n2 = end - mid;
int *L = malloc(sizeof(int) * (n1 + 1));
int *R = malloc(sizeof(int) * (n2 + 1));
for (i = 0; i < n1; i++)
L[i] = a[start+i];
for (j = 0; j < n2; j++)
R[j] = a[mid+1+j];
L[n1] = R[n2] = 0x7fffffff;
i = j = 0;
for (k = start; k <= end; k++) {
if (L[i] < R[j]) {
a[k] = L[i];
i++;
} else {
a[k] = R[j];
j++;
}
}
free(L);
free(R);
}
void merge_sort(int a[], int start, int end)
{
int mid;
if(start < end) {
mid = (start + end) / 2;
merge_sort(a, start, mid);
merge_sort(a, mid + 1, end);
merge(a, start, mid, end);
}
}