LinuxQuestions.org - Quicksort algorithm's incomplete implementation in book, in the C language.

- Programming (https://www.linuxquestions.org/questions/programming-9/)

- - Quicksort algorithm's incomplete implementation in book, in the C language. (https://www.linuxquestions.org/questions/programming-9/quicksort-algorithms-incomplete-implementation-in-book-in-the-c-language-4175726130/)

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) {

Quote:

Originally Posted by ajiten (Post 6437272)

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?).

Quote:

Originally Posted by pan64 (Post 6437279)

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.

Quote:

Originally Posted by NevemTeve (Post 6437278)

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.

Quote:

Originally Posted by GazL (Post 6437295)

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().

Hi

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:

https://www.geeksforgeeks.org/generi...lgorithm-in-c/

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.

Quote:

Originally Posted by ajiten (Post 6437305)

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.

yeah that's show you how to do things books for you, they're incomplete, you'd probably have better luck googling it

https://hackr.io/blog/quick-sort-in-c
https://www.geeksforgeeks.org/quick-sort/

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

Quote:

Originally Posted by EdGr (Post 6437340)

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.

Quote:

Originally Posted by NevemTeve (Post 6437278)

When you need to access the individual pointers within the pointer-array, you can write simply:
...
[/code]

Please tell why the pointer to the comparator function need be passed as a parameter, in all of the book's functions.

If possible give an smallish example, for emphasizing.

Passing the compare function as a parameter makes the C library quicksort generic. A fully generic quicksort would also be passed a swap function.
Ed

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).