Implementation of a quicksort function

Question

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 <time.h>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>

//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;
    }
}

int Descending  (long long x,long long y) {
    return ( !(Ascending(x,y)) );
}


long long my_random(long long min, long long max) {
    long double result;
    result = ((double)rand() / ((double)RAND_MAX + 1.0));
    result = (result * (max - min));
    result += min;
    result = (long long) result;
    return result;
}

void my_swap(long long* a, long long* b) {
    long long temp = *a;
    *a = *b;
    *b = temp;
}

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

    //Randomly selecting the pivot.
    long long random_index  = my_random(begin,end);
    long long pivot;
    my_swap(&array[begin],&array[random_index]);
    pivot = array[begin];

    //Partion matheod used : Hoare partition.
    long long i  = begin - 1;
    long long j  = end   + 1;

    while(TRUE) {
        do {
            j--;
        } while (!(cmp(array[j],pivot)) && array[j] != pivot);


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


        if (i < j) {
            my_swap(&array[i],&array[j]);
        }
        else {
            return j;
        }
    }
}

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

    if (begin < end) {
        long long q = quicksort_partition(array, begin, end, cmp);
        quicksort(array, begin  , q, cmp);
        quicksort(array, (q + 1),  end   , cmp);
    }
}

Please point out the bad practises used here and help me to rectify them.

Answer 1

Here are some things I noticed that might help you improve your code.

Use stdbool

Instead of defining your own values for TRUE and FALSE, you might consider instead using #include <stdbool.h> which defines true and false.

Use a consistent naming strategy

Some of your functions are uppercase as with Ascending, others have an underscore as with quicksort_partition and still others omit the underscore as with printarray. The names, of course, are all legal C and the compiler doesn't care, but other people reading your code will find it easier if you use a consistent naming strategy for both functions and variables.

return is not a function call

Because return is not a function call, parentheses are generally not used when returning a value. Thus instead of this:

int Descending  (long long x,long long y) {
    return ( !(Ascending(x,y)) );
}

you could write this:

int Descending  (long long x,long long y) {
    return !Ascending(x,y);
}

Although technically, it would be a bit better to write it instead like this to avoid the negation operation:

int Descending  (long long x,long long y) {
    return Ascending(y,x);
}

Simplify your code

The Ascending function could instead be written as a single line:

int Ascending   (long long x,long long y) {
    return x < y;
}

This makes it much simpler to understand the code at a glance.

Similarly, the last two lines of my_random are currently these:

result = (long long) result;
return result;

But the penultimate line is completely useless. There is an implicit cast in the return and the explicit cast doesn't change the type of result which is long double so is useless.

Use const where possible

Your printarray function just prints the passed array and does not (and should not) modify the array. For that reason, the function prototype should instead look like this:

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

Avoid using long long for an array index

An index into an array is an int or a size_t and not a long long, so having the an index that is a long long doesn't actually give you a larger range -- it simply forces the compiler to cast (on platforms for which an int and long long are different sizes).

Reconsider the interface

The prototype for quicksort is currently this:

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

However, it would probably make more sense from a user's point of view to have that instead be this:

void quicksort( long long* array, size_t arraysize, p_compare_function cmp);

You'll still need your original version internally, but that's not the way a user would likely want to think about using this sort function, which brings me to the last point.

Define the interface clearly

For a function like this which has the potential to be reused, one would normally define an interface which would be in a header file, say, quicksort.h and an implementation file which would be in quicksort.c. The header file would contain only and exactly the public interface functions such as quicksort but not internal functions such as quicksort_partition. This gives the user just what is needed but hides the implementation details.

Answer 2

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 < min. In that case, the results could be weird.

quicksort

    quicksort(array, begin  , q, cmp);
    quicksort(array, (q + 1),  end   , cmp);

If you are going to do this, please keep the commas with the token before them:

    quicksort(array, begin,   q,   comparison_function);
    quicksort(array, (q + 1), end, comparison_function);

Also note that the spacing between end and cmp was simply wrong.

I also renamed cmp to comparison_function here. Given how little it's used, it seemed better to favor readability over convenience here. This is what Larry Wall calls true laziness -- commenting your code so that it's easier to read later. In application, you will spend more time reading code than writing it. It's only in the somewhat artificial environment of learning that you can spend more time writing code than reading it. So it's better to get in the habit of writing readable code than terse code.

Comparing

return ( !(Ascending(x,y)) );

You define Descending as not Ascending, however this gives the two of them different meaning. Something is Ascending if x < y but is Descending if x >= 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.