Implementation of a quicksort function

I am an absolute beginner to programming and am learning it using C. I have just learned function pointers and tried to implement a quicksort function using function pointers to determine the nature of sorting.

```
//Program implementing a quick-sort function using Hoare method
//to partition using a random pivot.
//Function pointer is used to determine the nature of sort (Ascending / Descending).
#include
#include
#include
#include

//Typedef: Function Pointer to be used for determining he nature of sort:
typedef int (*p_compare_function)(long long,long long);

enum BOOLEAN{FALSE,TRUE};

//FUNCTION PROTOTYPES:

//Functions to be used for determining the nature of sort:
int Ascending (long long x,long long y);
int Descending (long long x,long long y);

//Generates a random number between a lower and a upper limit.
long long my_random(long long min, long long max);

//Functions to be used for the actual functioning of the algorithm:
void my_swap(long long a, long long b);

long long quicksort_partition( long long* array, long long begin,
long long end, p_compare_function cmp);

void quicksort( long long* array, long long begin, long long end,
p_compare_function cmp);

void printarray(long long *pArray, long long nSize);

int main() {

srand(time(NULL));

long long array[] = {5,2,9,7,3,1,6,8,4,0,4,3,5,67,22,3,644,335,345,24,
33,25,22,5,2,43223,4};

long long arraysize = sizeof(array)/sizeof(*array);

//Testing
quicksort(array,0,arraysize-1,Ascending);
printarray(array,arraysize);

quicksort(array,0,arraysize-1,Descending);
printarray(array,arraysize);

return 0;
}

void printarray(long long *pArray, long long nSize) {
for (long long i=0; i < nSize; i++) {
printf("%lld ",pArray[i]);
}
printf("\n");
}

int Ascending (long long x,long long y) {
if (x < y) {
return TRUE;
}
else {
return FALSE;
}
}

Definitions

//FUNCTION PROTOTYPES:

Given that you have everything in one file, you could simply change the declaration order and get rid of these. Function prototypes are necessary only when you are linking multiple files together (or in the odd case of two or more functions that call each other circularly). They are overkill here.

int Ascending   (long long x,long long y);
int Descending  (long long x,long long y);

While the compiler won't care, adding spaces between the function name and the parameters list makes this look like something other than a function to me. I.e. I find this notation confusing.

main

long long arraysize = sizeof(array)/sizeof(*array);

There is a type explicitly for handling size data. You may think that you are being more inclusive by using long long, but you are actually moving errors from where the problem occurs to where clipping occurs. In programming, it is generally better to be consistent than right. Because even if you are more right, you will be wrong in your interactions.

size_t array_count = sizeof(array) / sizeof(*array);

The size_t type is what is used in library functions dealing with sizes. Using it here means that if you add an additional sort that does a malloc, that you will be using the right type.

I also changed the name of the variable. One, because I prefer the name count for something that represents the number of elements in a collection. Two, because words should be separated by something. In C, the standard is to use underscores. In other languages, they often use casing to indicate where new words begin (I disagree with that actually, but at least it is common). It's much easier to read if you use something to say where new words begin. Otherwise, the reader has to think about it when we want the reader's attention on what the code is doing.

Similarly, I added spaces around the /. This makes it easier to see where one token ends and another begins.

I didn't change it here, but I would prefer a name like data or sample_data instead of array. I can easily see the type of the variable. What I want to know is what it represents. Thus, sample_data or test_data would best tell me what I wouldn't otherwise know from the declaration.

quicksort(array,0,arraysize-1,Ascending);

Again, I'd find this easier to read with more spacing.

quicksort(array, 0, array_count-1, Ascending);

You could also add spaces in array_count - 1, but it's not strictly necessary.

my_random

result = (long long) result;

This does a double cast. Since result is a long double, this casts to long long and then back to long double. Presumably that's not what you wanted. Instead, use a different variable on the left hand side. Note that you should probably add min after the cast rather than before.

Your max value is inclusive, meaning that it's a valid result from this function. However, you add 1.0 to MAX_RAND which makes it exclusive of the upper bound. I.e. result will never be 1.0. This seems incorrect.

You also just cast from floating point to integer, which drops the fractional part. This will tend to bias the result down.

size_t my_random(size_t min, size_t max) {
    long double intermediate;
    size_t result;

    intermediate = (double)rand() / (double)RAND_MAX;
    intermediate *= max - min;

    result = (size_t) (intermediate + .5);
    result += min;

    return result;
}

Now it's clear where we are doing casts. We have a declarations section, a floating point section, an integer section, and a return section. We do only one implicit cast (to max - min which is cast to long double by the multiplication). All other operations are done with variables that are already of the same type.

I still have one problem with this. It's quite possible for max - min to be larger than RAND_MAX. If that happens, there are some potential pivots that we'll never pick.

Also, this function is not robust if max = y. Better might be

// Descending is the reverse of Ascending
return Ascending(y, x);

This is a little harder to follow but it now makes it Descending if y < x. Another way to put this is that it is now Ascending in the opposite direction.

}while ((cmp(array[i],pivot)) && array[i] != pivot);

This logic can also be simplified then. Because all our comparison functions only return TRUE for a strict inequality, we don't need an extra inequality check on this one (the other is still needed).

} while ( cmp(array[i], pivot) );

Note that qsort gets around this by demanding that the comparison functions return zero for equality and positive or negative values for inequalities.

StackExchange Code Review Q#75409, answer score: 4