As you know that GNU-C provides qsort() function in <cstdlib> in this prototype

You may know about Selection Sort Algorithm already, I want to write a function to perform Selection Sort but it can apply generally for many type: int, long, float, double... like qsort() above.
How can I do that?

Rewrite qsort in generic way first - in C++.

No, I don't wanna use C++ template.
I want a pure C curiously, either generic through void* or Macro

If you want a generic type and just one function, in "C" you'll have to specify the type at runtime and use a chain of ifs or 'switch' to acti according to the specified type.

It won't look nice.

I'm not looking for whether it is nice or not, I just want to learn to know how to do it.
Would you mind giving the sample on my request above?

Add a 'type' parameter.

Define a number of macros - like

,

etc.

Then in the rewritten 'qsort' write:

@Sergei: thanks for macro guiding. However, what if my data-type is a structure?

You add a macro per structure you are going to use as array to be sorted element and the corresponding case to 'switch' statement.

Because of questions/issues like this 'qsort' implies a user provided comparison routine. The same approach is used in, for example, Perl WRT its built-in 'sort'.

No program can know beforehand all possible types to be used.

I'm probably missing some subtle point given that I'm more of a C++ than C programmer but the key to this is the compare function that you pass in. All of the data is provided without having to pass in the type of the data being sorted. You have a pointer to the array, the number of elements and the size of each element.

create a character array that overlays the array passed in
char *a = base;

set up a key for comparison
void * key;
key = (char *)malloc(size); // check this allocation worked

assign the value to be compared in to key
memcpy(key, &a[j*size],size);
Where j is the element you are interested in

repeat for the second element, since a compare will require two element, throw in you appropriate loops and, do a swap on the array when you have found the minimum value using memcpy().

Finally free up all memory allocated, ie the key(s).

Why do you need the key in the first place?

The key is the data item that you use to sort. Technically in a generic algorithm what I called the key is the whole data stored in the array and that could be the key or the key could be a part of that item, or even held elsewhere if the data item is a pointer.

But without a key there would be no way of knowing which item comes before the other and that is delegated to the compare function with two key values passed to it.

Problem solved!
I now can make it exactly like qsort() but with selection sort algorithm
Thanks all for helping me so much.

What I'm asking is, why can you not do something along these lines:

The only place where the type of the elements must be used in a sorting function is in the comparison function. Simply using an appropriately constructed comparison function permits the sorting routine to sort any fixed-sized array of fixed-sized objects, whether the sorting key in the object involves integers, floating-point numbers, compiler symbol table entries, or telephone book entries.

The sorting function chooses two elements of the array at each iteration, and puts those two elements in order. The method used to choose which two elements to sort at each step determines what sorting algorithm the sorting function implements.

The sorting function computes the (void *) addresses of the two chosen elements of the array using the (void *) address of the start of the array, the size_t indices of the two elements selected from the size_t number of elements in the array, and the size_t size of an array element.

The sorting function passes these two (void *) addresses of the selected two elements to the comparison routine. Depending on the result of the comparison, the sorting routine may need to swap those two elements.

The swap operation can be implemented in such a way that it needs to know only the size_t size and the (void *) addresses of the two items it needs to swap. The swap operation also needs a temporary storage buffer the size_t size of the array elements. The swap function need not be abstracted as a separate function from the sorting function. It is typically only three lines of code.

Then the sort function selects the next pair of items.

The sort function repeats this process until all items have been compared, swapping items as indicated by the comparison algorithm.

To sort an array of a different type of item, you need only write a comparison function which knows how to compare two items of that type. Separating the comparison function from the sorting function permits functional abstraction of the sorting algorithm from the sorting function so that the same algorithm can be used to sort any sort of items that contain sortable keys.

You can easily change the item selection code to implement other sorting algorithms. If you are sorting more than a few items (a dozen items or so) you should see tremendous performance penalties for using the selection sort compared to quick sort or heap sort algorithms. Insertion sort will become relatively *much* slower than quick sort or heap sort with a thousand items. How many entries are there in a phone book?

Implementing this sorting function in C should give you a clear understanding of how to achieve functional abstraction in C by using pointers to functions.

1 members found this post helpful.

@Arthur: yes, u're right. That's what I tried to achieve, and now I can do it ^^!