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

• MarcDefiant: en.wikipedia.org/wiki/Insertion_sort#Variants
• Aseem Bansal: @MarcDefiant Thanks for the link but instead of changing the algorithm I just wanted reviews about the currently implemented algorithm. Although they are variants of this algorithm they are different algorithms.
• Vedran Šego: It'd be better if your sort was done on a linked list, as inserting elements to an array is very slow.
• Aseem Bansal: @VedranŠego I didn't understand what you said. Are you talking about the main function?
• Vedran Šego: Sorry, I've mixed something up. Linked lists would make search slower, so the overall complexity would be O(n^2), just like in your case.

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...

• Aseem Bansal: About defining temp and k inside the for loop. I don't know about C++ but in C wouldn't that have significant more overhead in case of outer loop iterating over large ranges? Also wouldn't declaring loop variables at the beginning of a function better if they are reused instead of declaring them again and again?
• William Morris: No, in C there is no extra overhead associated with exactly where you define a variable. The compiler will handle such things optimally without your needing to care. And defining a loop variable in each loop instead of once at the beginning of the function incurs absolutely no overhead. On the plus side though it reduces the scope of the variable, which is always good - the reader knows for sure that it is not used outside the loop in which it is defined.
• Aseem Bansal: Can you add something about errno. I haven't used it ot perror() before. In my code the output of overflow is shown on the console itself. Is that the correct behaviour? Also I have updated the code. Please give your comments about that.
• William Morris: Every process on Unix etc has a global error number variable named errno set by failing system/library calls. Take a look at the Wikipedia page on errno or look at the manual pages on your system (type man perror).