8
88888 Dihedral
Ben Bacarisseæ–¼ 2011å¹´12月29日星期四UTC+8下åˆ7時58分14秒寫é“:
This will turn the quick sort algorithm to be of O(nlog(n)) in speed
and O(n) used for the heap space.
Thus the non-choking merge sort is a distributed system is better.
Of course sorting integers of 32 bits in a radix sort of billions of items
in an 64 bit OS is the obvious way to replace the quick sort in the standard
library of C.
An array of 32 bit integers can be decomposed as 12-12-8 in 3 passes or 16-16 in two passes in a descent radix sort implementation that needs the O(n) chunk
in the heap space.
Stone said:Here's the problem.
I wrote a function 'int my_compare(const void *, const void *);' and
passed it to qsort() of stdlib.h, in order to sort an array named
*ptr* which contains indices of another array *data*. By that I
intended to sort elements of *ptr* (i.e. ptr) using data[ptr] as
the key value.
However, the *data* array was defined as static in main(), and seemed
not easy to access in my_compare(). Is there any way to achieve this?
You can either move the array so that it is defined at file scope
(i.e. outside main) or you can arrange for there to be a file-scope
pointer to it:
#include <stdlib.h>
#include <stdio.h>
int *aux_sort_ptr;
int my_compare(const void *p1, const void *p2)
{
const int *ip1 = p1, *ip2 = p2;
return aux_sort_ptr[*ip1] - aux_sort_ptr[*ip2];
}
int main(void)
{
static int data[] = { 3, 1, 2 };
int idx[] = { 1, 2, 3 };
aux_sort_ptr = data;
qsort(idx, sizeof idx/sizeof *idx, sizeof *idx, my_compare);
for (int i = 0; i < sizeof idx/sizeof *idx; i++)
printf("idx[%d] = %d, data[%d] = %d\n",
i, idx, idx, data[idx]);
}
This is ugly (and problematic in threaded code), but there's no elegant
way round it using standard C. Many systems have other sort functions
whose comparison function can be handed another void * (see Dr Nick's
reply) but I don't think and have become common enough to though of as
"almost standard".
This will turn the quick sort algorithm to be of O(nlog(n)) in speed
and O(n) used for the heap space.
Thus the non-choking merge sort is a distributed system is better.
Of course sorting integers of 32 bits in a radix sort of billions of items
in an 64 bit OS is the obvious way to replace the quick sort in the standard
library of C.
An array of 32 bit integers can be decomposed as 12-12-8 in 3 passes or 16-16 in two passes in a descent radix sort implementation that needs the O(n) chunk
in the heap space.