ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
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?
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?
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.
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?
@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).
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.
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.
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.