4
\$\begingroup\$

I have started studying algorithms using the classic CLRS book and decided to hone my C skills at the same time.

I wrote this function implementing insertion sort in C. I have tested it and verified that it works correctly. I would like to know whether it is readable and follows best practices.

Some points I'd like to receive feedback on:

1) Are the variable names well chosen? I have the impression that the convention in C is to use shorter names than in other languages and chose parameter names like arr and n accordingly. Would names like array and array_size have been better instead?

2) Instead of an array, the calling code could pass a null pointer to the function. I handle that using an int return value. Is that the best response?

3) Are the comments explaining the inner loop necessary?

#include <stddef.h>

#define INVALID_PARAMETER 1

/* Sorts an array of ints in-place using insertion sort.
 * Returns INVALID_PARAMETER if a null pointer is passed
 * as argument and 0 otherwise.
 */

int insertion_sort(int arr[], size_t n)
{
    if (arr == NULL) {
        return INVALID_PARAMETER;
    }

    for(size_t i = 1; i < n; i++) {
        int key = arr[i];

        /* Look through the array backwards until finding where key must be
         * inserted. If the element we are looking at now is bigger than key,
         * it is displaced forward. Stop when an element smaller than key is
         * found or the start of the array is reached. */
        size_t j;
        for(j = i; j > 0 && arr[j - 1] > key; j--) {
            arr[j] = arr[j - 1];
        }

        /* After the loop, j is either 0, what means that no element smaller
         * than key was found and it must be the first element in the sorted
         * array, or j is the position after the first element found that was
         * smaller than key and so it is where key must be inserted. */
        arr[j] = key;
    }

    return 0;
}
```
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to code review, it might be better if you included the code that tests the function as well. That would provide a concrete programming example. \$\endgroup\$ – pacmaninbw Jul 30 at 1:16
2
\$\begingroup\$
  • Using a symbolic constant (INVALID_PARAMETER) along with a literal 0 as a return value is not the cleanest solution. As a side note, a return value signifying an error is traditionally negative.

  • The best kept secret of insertion sort is the fact that the j > 0 && arr[j - 1] > key termination condition of an inner loop is suboptimal. It tests two conditions in every iteration. It is possible to get away with only one test: check wether the key < arr[0] first. Consider an inner loop along the lines of key

        int j;
        if (key < arr[0]) {
            // Now key shall for sure become leftmost. Don't bother testing values.
            for (j = i; j > 0; j--) {
                arr[j] = arr[j - 1];
            }
        } else {
            // Now arr[0] is a natural sentinel. Don't bother testing indices.
            for (j = i; key < arr[j - 1]; j--)
                arr[j] = arr[j - 1];
            }
        }
        arr[j] = key;
    
  • Otherwise, LGTM.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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