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