Sorting an int[] array using insertion sort algorithm - follow-up

Question

Previous questions:

1. Is my implementation of insertion sort is correct?
2. Sorting an int[] array with an Insertion Sort

I'm currently learning about different sorting algorithms and after reading on the concept of the insertion sort of how it's done I've tried to implement it by myself before seeing how it was implemented in the source from which I'm learning.

This is my implementation:

void insertionSort(int arr[]) { for(int i = 1; i < SIZE; i++) { int value = arr[i]; int j = i; for(; j > 0; j--) { if (value < arr[j - 1]) { arr[j] = arr[j - 1]; } else { break; } } arr[j] = value; } } 

Now I think I've implemented it correctly (not talking about efficient or anything just the algorithm itself), but when I saw the way it was implemented in the course I'm seeing I had a bit of concerns about my implementation because they're really different and I just wanted to make sure my implementation is really an insertion sort algorithm implementation and I didn't done anything else.

Here's the implementation by the source I'm learning from:

void insertionSort(int arr[]) { for(int i = 1;, i < SIZE; i++) { int value = arr[i]; int j = i - 1; int done = 0; do { if (arr[j] > value) { arr[j + 1] = arr[j]; j--; if (j < 0) done = 1; } else { done = 1; } } while(!done) arr[j + 1] = value; } } 

Is my implementation of insertion sort correct ?

Also I would appreciate if you could compare my implementation to the one made by the source I'm learning from, any efficiency differences or any other thing you think would worth mentioning.

Answer 1

Nice job. It looks like you have implemented a correct insertion sort.

The inner loop could be better written: the j > 0 condition is giving an incomplete picture of how the loop terminates.

One other change you should make is to take a size parameter for the array size. Without it, you have a function that only works on arrays of a specific size! If you look at examples of functions in the C library, almost every function that takes an array also takes another parameter to specify its size. Usually, the type of that parameter is an unsigned int, but called size_t to make its purpose clear.

#include <stdlib.h> void insertionSort(int arr[], size_t size) { for (int i = 1; i < size; i++) { int value = arr[i]; int j; /* Shift elements over by one slot to make way for the insertion */ for (j = i; j > 0 && value < arr[j - 1]; j--) { arr[j] = arr[j - 1]; } arr[j] = value; } } 

Your implementation is better than the book you're learning from. In fact, I would recommend using a different book, if the code examples are so poor. Specifically, the biggest problem is the done flag. Setting a flag to be inspected by a conditional elsewhere is a cumbersome way to implement flow control. Your break is much more direct and assertive, and I think that my loop condition is even clearer.