Quicksort algorithm's incomplete implementation in book, in the C language.
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.
Quicksort algorithm's incomplete implementation in book, in the C language.
Want to generate a complete code to the program for Quicksort code, given incomplete in the book: Algorithms in a nutshell, by George T. Heineman.
The book states the below parts, leaving out the main(), cmp(), selectPivotIndex functions' implementation to the user.
Code:
void sortPointers(void **vals, int total_elems, int(*cmp)(const void *, const void *))
{
do_qsort(vals, cmp, 0, total_elems-1);
}
void do_qsort(void **ar, int(*cmp)(const void *, const void *), int left, int right)
//left is for the start/left index position in the array/sub-array. Similarly, for the right variable.
{
int pivotIndex;
if(right<=left) return;
//partition
pivotIndex = selectPivotIndex(ar, left, right);
pivotIndex = partition(ar, cmp, left, right, pivotIndex);
if(pivotIndex - 1 - left<= minSize) //to have a lesser time complexity method, for lesser size of the input array/sub-array.
insertion(ar, cmp, left, pivotIndex-1);
else
do_qsort(ar, cmp, left, pivotIndex-1);
if (right - pivotIndex -1 <= minSize)
insertion(ar, cmp, pivotIndex+1, right);
else do_qsort(ar, cmp, pivotIndex+1, right);
}
/*partition ar{left, right] around a given pivot element, ar[pivotIndex], in linear time; by storing pivot into its pivot location.
The location of pivot, is given in store , s.t. all ar[left, store) <= pivot, and all ar[store+1, right] > pivot. */
int partition(void **ar, int(* cmp)(const void *, const void *), int left, int right, int pivotIndex)
{
int idx, store;
void *pivot = ar[pivotIndex];
/*move pivot to the end of the array*/
void *tmp = ar[right];
ar[right] = ar[pivotIndex];
ar[pivotIndex] = tmp;
//all values sorted in two sub-arrays, i.e. <= pivot, and > pivot. The values <= pivot are moved to front of the (sub)array, & pivot inserted just after them.
store = left;
for(idx = left; idx < right; idx++)
{
if(cmp(ar[idx], pivot) <= 0)
{
tmp = ar[idx]; ar[idx] = ar[store]; ar[store] = tmp; store++;
}
}
tmp = ar[right]; ar[right] = ar[store]; ar[store] = tmp;
return store;
}
Will ask few question, in a sequential manner - one at a time, else risk adding to confusion.
The use of: void **vals, as parameter for passing array, seems confusing to me; and request what is the reason for using a double indirection pointer.
I mean the job can be done by a single indirection pointer too, then why was a double indirection pointer needed?
When you need to access the individual pointers within the pointer-array, you can write simply:
Code:
void do_qsort(void **ar, int(*cmp)(const void *, const void *), int left, int right) {
ar[left] -- the first pointer to work with
ar[right] -- the last pointer to work with
}
Otherwise you should write:
Code:
void do_qsort(void *ar, int(*cmp)(const void *, const void *), int left, int right) {
((void **)ar)[left] -- the first pointer to work with
((void **)ar)[right] -- the last pointer to work with
}
Here is a synonym for the original:
Code:
void do_qsort(void *ar[], int(*cmp)(const void *, const void *), int left, int right) {
Another:
Code:
typedef void *AnyPtr;
void do_qsort(AnyPtr ar[], int(*cmp)(const AnyPtr, const AnyPtr), int left, int right) {
The use of: void **vals, as parameter for passing array, seems confusing to me; and request what is the reason for using a double indirection pointer.
I mean the job can be done by a single indirection pointer too, then why was a double indirection pointer needed?
This is the usage of strict types.
void **vals means: vals is a pointer, and the location (where it points) contains also a pointer.
So you declare: vals is a pointer to a pointer
From the other hand: void *vals means vals is just a pointer, but we don't know anything about that location (if it points to a string, integer or what?).
This is the usage of strict types.
void **vals means: vals is a pointer, and the location (where it points) contains also a pointer.
So you declare: vals is a pointer to a pointer
From the other hand: void *vals means vals is just a pointer, but we don't know anything about that location (if it points to a string, integer or what?).
But, I thought that the array pointed to by vals, gives the start location of the array; and the array itself contains the integers.
Seems, the book is using an array of pointers instead; and those pointers in different locations of the array, point to integers.
When you need to access the individual pointers within the pointer-array, you can write simply:
Code:
void do_qsort(void **ar, int(*cmp)(const void *, const void *), int left, int right) {
ar[left] -- the first pointer to work with
ar[right] -- the last pointer to work with
}
Otherwise you should write:
Code:
void do_qsort(void *ar, int(*cmp)(const void *, const void *), int left, int right) {
((void **)ar)[left] -- the first pointer to work with
((void **)ar)[right] -- the last pointer to work with
}
Here is a synonym for the original:
Code:
void do_qsort(void *ar[], int(*cmp)(const void *, const void *), int left, int right) {
Another:
Code:
typedef void *AnyPtr;
void do_qsort(AnyPtr ar[], int(*cmp)(const AnyPtr, const AnyPtr), int left, int right) {
Is it a must to have an array of pointers?
It seems from your answer that an array of integers, is not considered in the functions given; or an array of integers is itself an array of pointers!
Am confused as never thought either of the two options to be true, i.e. neither am clear that the given functions operate on an array of pointers; or the second option, which is a fundamental question - i.e. if the array of integers, is implemented as an array of pointers?
Imagine that instead of ints, you're sorting a bunch of large data structures. That's a lot of data to be swapping back and forth, so it makes sense to take the approach of sorting an index array of pointers to those objects rather than throwing the objects themselves about. That said you will need the unsorted index to exist before you start, but in most real-world cases, your code most likely already has one for other reasons.
Imagine that instead of ints, you're sorting a bunch of large data structures. That's a lot of data to be swapping back and forth, so it makes sense to take the approach of sorting an index array of pointers to those objects rather than throwing the objects themselves about. That said you will need the unsorted index to exist before you start, but in most real-world cases, your code most likely already has one for other reasons.
Fine, but the need to pass the comparator function: cmp, in all the 3 functions is unclear. Was it really needed, or just the partition function can call the cmp function, with no need for passing it as a parameter, to any of the given 3 functions?
Next, is unclear why the sortPointers function is being used? Its use seems redundant, and unnecessary to me, and just the function do_qsort should be directly called by the main().
I agree the void ** parameter is a bit confusing. And it doesn't allow other things than pointers to be sorted. I searched, and this is a little better:
Here they cast void* to char* so we can do "math" with the pointers. This allows sorting arrays of anything - not just pointers. Notice they also have a function for swap - you need it for big structures.
But you still need a comparison function. It has 2 pointers as parameters. I don't think its possible to make generic functions taking parameters without a type. And it wouldn't always for big structures.
Fine, but the need to pass the comparator function: cmp, in all the 3 functions is unclear. Was it really needed, or just the partition function can call the cmp function, with no need for passing it as a parameter, to any of the given 3 functions?
Next, is unclear why the sortPointers function is being used? Its use seems redundant, and unnecessary to me, and just the function do_qsort should be directly called by the main().
sortPointers is just a helper function.
It needs a list of pointers and a comparator function and will only call do_qsort. Obviously you can call it directly, without sortPointers.
Sorting arrays of pointers covers 95% of cases (actual count, not a made-up statistic).
A double indirection allows the same parameters to be passed to the swap and comparison functions if one has both.
Ed
Yes, usually we have chained list of pointers to structs. Or just an array of pointers to structs.
And we just reorder the pointers, not the structs themselves.
this is all about to have a generic solution. The implemented qsort knows nothing about the structure of the data behind the pointers, therefore you need to pass a list (of pointers) to it and a comparator function which knows exactly how can be the real data evaluated (compared) using those pointers.
The sorting algorithm itself is implemented in the qsort function and the real data type, data structure is completely irrelevant here.
Obviously you can do that in one single function, with embedded comparator functionality, without real cmp function, this is also implemented and used in special cases (for example when the speed is very important).
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.
