Here's a complete implementation taken (verbatim) from Stroustrup (The C++ Programming Language, 3rd ed., p. 158; comments added).
`cmp' is a comparison function (defined elsewhere).
How would you streamline this implementation to include a call to
qsort()?
Code:
void ssort(void* base, size_t n, size_t sz, CFT cmp) {
for(int gap = n/2; 0<gap; gap /= 2) // gap sequence is n/2**n
for(int i = gap; i<n; i++) // start at the second ``row''
for(int j=i - gap; 0 <= j; j -= gap) {
char* b = static_cast<char*>(base);
char* pj = b +j*sz;
char* pjg = b+(j+gap)*sz;
if(cmp(pjg,pj))<0 {
for(int k=0; k<sz; k++) {
char temp=pj[k];
pj[k] = pjg[k];
pjg[k] = temp;
}
}
}
}
See the wikipedia article for details.
I was thinking about pulling one column at a time from `b' and then sorting that column with a
call like qsort(column, ncol, sz, cmp), where `ncol' is the number of elements in that column:
Code:
12 18 52 9 8 5 17 8 1 5 30 16 46 7 8
-->
12 6 18 52 9
8 13 5 17 8
1 12 5 30 16
46 7 8
How would you select, say, only the green elements from the array, sort the green elements, and move on to the next column?