Implementation of insertion sort

Question

Information about my code:

I am following this MIT OCW algorithms course. The first lecture described insertion sort and merge sort. I implemented insertion sort in C.

The algorithm is structured as a function called from the main function. The array to be sorted is allocated dynamically in the main function but can also be statically allocated.

What I am looking for:

I am looking whether the code can be optimized without changing the algorithm (insertion sort), whether it follows the best-practices of programming in C and does it have proper readability factor?

#include<stdio.h>
#include<stdlib.h>

void insertion_sort(int arr[], int length)
{
    /*
    Sorts into non-decreasing order
    To change the sorting to non-increasing order just change
    the comparison in while loop
    */
    register int j, k;
    int temp;

    for(j = 1; j < length; j++)
    {
        temp = arr[j];
        k = j - 1;
        while (k >= 0 && arr[k] > temp)
        {
            arr[k + 1] = arr[k];
            k--;
        }
        arr[k + 1] = temp;
    }
}

int main()
{
    int length;
    register int i;
    int *arr;

    //Finds the length of array and dynamically creates array of that length
    scanf("%d", &length);
    if ( (arr =  (int *)malloc(sizeof(int) * length)) == NULL)
    {
        printf("Not enough memory");
        return 1;
    }

    //Reads the array
    for(i = 0; i < length; i++)
        scanf("%d", &arr[i]);

    //Calls the sorting algorithm
    insertion_sort(arr, length);

    //Prints the sorted array
    for(i = 0; i < length; i++)
        printf("%d ", arr[i]);

    //Frees the memory allocated and returns
    free(arr);
    return 0;
}

Answer 1

I cannot offer any optimization, only a few comments on best practice (as I see it). There's very little to say; the code is nice.

• Use of register is unnecessary (and hence rare). The compiler may well ignore it and it probably has a better idea of what to put in registers than you or I.

• It is best to define variables nearer to where they are first used. This reduces their scope and makes for easier reading. For example in insertion_sort I would do:

  for(int j = 1; j < length; j++)
  {
      int temp = arr[j];
      int k = j - 1;
      while (k >= 0 && arr[k] > temp)
      ...
  

  So I defined the loop variable j in the loop and temp and k at the point of first use. (This makes even more sense in C++ where an early definition incurs the overhead of a default construtor call.)

• Your while-loop could arguably be a for-loop. A for-loop makes the loop conditions more immediately obvious, but in such a short loop it makes no difference.

• In main you cast the return from malloc. This is necessary in C++ but not in C. And on an error in system and library calls that set the global errno, such as malloc, I would use perror("malloc") which will print a relevant error message to stderr, instead of rolling your own with printf (which prints to stdout).

• Again your for-loops in main would be better defining loop variable i in the loop. Also these loops should have braces:

  for (int i = 0; i < length; i++) {
      scanf("%d", &arr[i]);
  }
  

  Strictly speaking braces are not necessary but they are considered good practice, as they prevent a class of error such as someone adding a printf:

  for (int i = 0; i < length; i++) 
      scanf("%d", &arr[i]);
      print("%d", &arr[i]);
  

• For safety, you should always check user input before using it, such as length here.

• Your comments in main are really just stating the obvious and as such could be considered 'noise'. The comment in insertion_sort on the other hand is more useful, although 'non-decreasing' and 'non-increasing' are odd ways to say 'increasing' and 'decreasing' respectively.

• Really nit-picking, I prefer a space after for and while and no space between brackets in the expression if ((arr = malloc(sizeof...