3
\$\begingroup\$

Here's my second program in C, and my time/space analysis of this code.

I have been reading Modern C and I attempted this challenge on page 26. The prior pages are pretty much the only exposure I have had to C, for reference. I have a rough understanding of pointers but I have read no formal material on the subject.

Ideas which I have not yet encountered

  • test harnesses
  • function contracts
  • array slices
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

// sort the subset of array whose first and last elements have indexes range_start and range_end, respectively
void quick_sort(size_t range_start, size_t range_end, double array[]) {
    // the sub-array is trivially sorted, or has size 0
    if (range_start >= range_end) {
        return;
    }

    double current_element = array[range_start];
    double const pivot = array[range_end];

    // the array is overwritten at these indicies
    size_t free_lower_index = range_start;
    size_t free_upper_index = range_end;    

    while (free_lower_index + 1 < free_upper_index) {
        if (current_element >= pivot) {
            array[free_upper_index] = current_element;
            current_element = array[--free_upper_index];
        } else {
            array[free_lower_index] = current_element;
            current_element = array[++free_lower_index];
        }
    }

    // now, free_lower_index and free_upper_index are adjacent
    if (current_element >= pivot) {
        array[free_lower_index] = pivot;
        array[free_upper_index] = current_element;
    } else {
        array[free_lower_index] = current_element;
        array[free_upper_index] = pivot;
    }

    // the elements in the lower subarray are all < pivot
    quick_sort(range_start, free_lower_index, array);
    // the elements in the upper subarray are all >= pivot
    quick_sort(free_upper_index, range_end, array);
}

// returns true if the input is sorted
bool self_test(size_t num_elements, double array[num_elements]) {
    for (size_t i = 0; i < num_elements-1; ++i) {
        if (array[i] > array[i+1] ) {
            return false;
        }
    }
    return true;
}

int main(int argc, char* argv[argc+1]) {
    printf("you want me to sort an array of length %d?\n", argc-1);
    
    if (argc < 2) {
        printf("you must provide at least one double to be sorted!\n");
        return EXIT_FAILURE;
    }

    // allocate some memory to store an appropriate number of double values
    double A[argc-1];

    // process args
    char* err;
    for (size_t i = 1; i < argc; ++i) {
        // arg -> double
        double const a = strtod(argv[i], &err);
        if (*err != 0) {
            printf("bad input! %s isn't a valid double\n", argv[i]);
            return EXIT_FAILURE;
        }
        A[i-1] = a;
    }

    // quick sort!
    // the input array has length argc-1, so the last element has index argc-2
    quick_sort(0, argc-2, A);

    printf("here is your sorted array:\n");
    for (size_t i = 0; i < argc - 1; ++i) {
        printf("%f\n", A[i]);
    }

    if (self_test(argc-1, A)) {
        printf("self-test passed\n");
    } else {
        printf("self-test failed\n");
        return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}

Complexity analysis

Here, I will assume the average case scenario, where the pivot element happens to be the median element of each sub-array to be sorted.

For ease of calculation I will also assume that n, the number of elements to be sorted, is an exact power of 2.

Time complexity

In each call to quick_sort, the pivot element is compared to every other element of the sub-array to be sorted, so this is roughly k comparisons, where k is the length of the sub-array.

With each recursive call, k shrinks by a factor of 2. But the number of recursive calls with this k also grows by a factor of 2.

So in total, the number of comparisons is: n + 2*(n/2) + 4*(n/4) + ... + n*(n/n)

This is n*ln(n) comparisons, so the time complexity is O(n*ln(n)) in the average case.

Space complexity

We require O(n) space for parsing arguments.

Given the assumptions above, quick_sort is called to a maximum depth of ln(n). In each call, we only require constant space.

So the space complexity is O(ln(n)) in the average case, ignoring the space required for parsing arguments.

\$\endgroup\$
4
  • \$\begingroup\$ If the pivot is the median element, that's actually the best case, not average. Worst case is when the pivot is the min or max, and average case is at either of the quartiles. Other than that, nice question! \$\endgroup\$ Commented Mar 13, 2023 at 13:05
  • \$\begingroup\$ @TobySpeight yes, you're right! I guess the average case would be have to be something like "the pivot isn't too close to the media element, but not too far away". I don't immediately see a way to quantify this so I'm going to leave my original question as-is. \$\endgroup\$ Commented Mar 13, 2023 at 13:24
  • 1
    \$\begingroup\$ @user14464173, What are the review goals? \$\endgroup\$ Commented Mar 14, 2023 at 14:05
  • 1
    \$\begingroup\$ @chux-ReinstateMonica I am learning C using the book I linked, and I would like some human feedback on my progress. \$\endgroup\$ Commented Mar 14, 2023 at 21:17

3 Answers 3

5
\$\begingroup\$

Still looks pretty good!

Beware Mixing Signed and Unsigned Integers

Because of the default type-conversion rules, you could get bugs like the famous 3U < -1. There are a few instances in your program where that might potentially become dangerous:

double A[argc-1];
/* ... */
for (size_t i = 0; i < argc - 1; ++i)

(I’ve deleted some feedback on your use of argc that was incorrect because I originally misunderstood the way the input to the program is formatted.)

Now, in this program, you already checked for the error argc < 2, so argc cannot be 0, which means the implicit conversion size_t(argc-1) cannot wrap around to SIZE_MAX. But it’s something to look out for in general, and could become a bug attractor if main ever gets refactored.

It would be better to define const size_t nelems = argc-1; or even const size_t nelems = (size_t)argc - 1U;. This probably doesn’t change the generated code because your compiler will perform common-subexpression elimination, but this definition of nelems is easier for a human to understand and has the correct type. Alternatively, if you do want to take the differences of pointers or indices, the signed type you want, for both the difference and your loop control variable, is ptrdiff_t.

GCC, Clang or ICX all will warn you about these implicit conversions if you give them the -Wconversion flag. (I recommend at least -Wall -Wextra -Wpedantic -Wconversion.)

Consider calloc over Variable-Length Arrays

Even though array expressions such as the double A[var-1] above are formally in the C Standard, some compilers, such as Microsoft Visual C, do not support them, and others deprecate them. They are very much second-class citizens in C.

The more common way to write them is something like

double* const array = calloc(num_elems, sizeof(double));

followed by a check that array is not a null pointer. This does force you to free(to_sort) later manually. As for the variable name A?

Use the Least Surprising Names

There’s some leeway on things like snake_case versus camelCase, but all-caps identifiers like A are almost always macros. Programmers would expect it to be a compile-time constant.

You also have both A and a in the same context, and even the line

A[i-1] = a;

I’ve always avoided things like that; they’re easy to typo (especially if my shift key is flaky) and hard to talk about verbally.

\$\endgroup\$
4
\$\begingroup\$
  • No naked loops

    Every loop implements an important algorithm, and therefore deserves a name. In your case, the loop

     while (free_lower_index + 1 < free_upper_index) {
         ....
     }
    

    partitions the array, and it wants to be a

     size_t partition(size_t start, size_t end, double array[])
    

    function, returning the landing index of the pivot. Then it could be reused, unit tested, etc. Just to give you a perspective, it is in the C++ standard library.

  • setf_testing() sounds like a misnomer. In fact, it implements yet another very important algorithm: is_sorted(....). which is also in the C++ standard library.

  • Upper index is better to not belong to the range, The + 1 in the condition

      free_lower_index + 1 < free_upper_index
    

    feels very unnatural.

\$\endgroup\$
3
\$\begingroup\$

General Observations

Good use of the current C programming standard. The code is basically well written, but variable names could be improved, at least in main().

I find it interesting to see both iteration and recursion in the same function. Iterative solutions are generally preferred over recursive solutions because of the increased use of system resources on recursion (pushing functions onto the stack and popping functions off the stack increases memory use as well as adding overhead).

Use Compiler Warnings to Write Better Code

In the old days before releasing code to user test we would run lint to reduce the possible number of bugs in the code. These days compilers can perform most of the issue checking that lint performed if the proper compiler flags are used.

I compiled this code using gcc on Windows 10 with the following flags:
-Wall
-Wextra
-pedantic
-Werror

and the following warning messages were generated:

comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare] main.c line 68
comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare] main.c line 83
conversion to 'size_t' {aka 'long unsigned int'} from 'int' may change the sign of the result [-Wsign-conversion] main.c line 80
conversion to 'size_t' {aka 'long unsigned int'} from 'int' may change the sign of the result [-Wsign-conversion] main.c line 87

line 68:

for (size_t i = 1; i < argc; ++i) {

line 83:

for (size_t i = 0; i < argc - 1; ++i)

The 2 warnings above are about comparing the variable i to argc, there are a couple of ways to deal with this, one would be to assign argc to a size_t variable and use that in the for loops:

    size_t loop_size = (size_t)argc;

    // process args
    char* err;
    for (size_t i = 1; i < loop_size; ++i) {

The other would be to cast argc to (size_t) in each of the loops.

line 80:

    quick_sort(0, argc-2, A);

The function quick_sort() expects the second argument to be size_t but it is int.

line 87:

    if (self_test(argc-1, A))

The function self_test() expects the first argument to be size_t. The correction for these 2 lines is similar to the first solution.

Local Functions Versus Global Functions

In a program as small as this it may not matter, but if there are local functions that should not affect the global namespace the functions should be declared as static. This is should in the example below for complexity.

Cyclic Complexity

While the main() function is not excessively complex (does too much) it could be simplified if there was a function to read in the data and another function to print the array. As programs grow in size the use of main() should be limited to calling functions that parse the command line, calling functions that set up for processing, calling functions that execute the desired function of the program, and calling functions to clean up after the main portion of the program.

static bool get_data(size_t data_count, char* user_input[data_count],  double data_array[data_count])
{
    char* err;
    for (size_t i = 1; i < data_count; ++i) {
        // arg -> double
        double const a = strtod(user_input[i], &err);
        if (*err != 0) {
            printf("bad input! %s isn't a valid double\n", user_input[i]);
            return false;
        }
        data_array[i-1] = a;
    }

    return true;
}

static void print_array(size_t data_count, double data_array[data_count])
{
    printf("here is your sorted array:\n");
    for (size_t i = 0; i < data_count - 1; ++i) {
        printf("%f\n", data_array[i]);
    }
}

int main(int argc, char* argv[argc+1]) {
    printf("you want me to sort an array of length %d?\n", argc-1);

    if (argc < 2) {
        printf("you must provide at least one double to be sorted!\n");
        return EXIT_FAILURE;
    }

    // allocate some memory to store an appropriate number of double values
    double A[argc-1];

    if (!get_data((size_t)argc, argv, A))
    {
        return EXIT_FAILURE;
    }

    // quick sort!
    // the input array has length argc-1, so the last element has index argc-2
    quick_sort(0, (size_t)argc-2, A);

    print_array((size_t) argc - 1, A);

    if (self_test((size_t)argc-1, A)) {
        printf("self-test passed\n");
    } else {
        printf("self-test failed\n");
        return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.