Thread: Insertion Sort

I stared the code for hours and still can't figure out what's the meaning of the following line of code.

Code:

#include <stdio.h>

void main( )
{
	int arr[5] = { 25, 17, 31, 13, 2 } ;
	int i, j, k, temp ;

	printf ( "Insertion sort.\n" ) ;
	printf ( "\nArray before sorting:\n") ;

	for ( i = 0 ; i <= 4 ; i++ )
		printf ( "%d\t", arr[i] ) ;

	for ( i = 1 ; i <= 4 ; i++ )
	{
		for ( j = 0 ; j < i ; j++ )
		{
			if ( arr[j] > arr[i] )  
			{
				temp = arr[j] ;
				arr[j] = arr[i] ;  

				for ( k = i ; k > j ; k-- )  //begin here
					arr[k] = arr[k - 1] ;

				arr[k + 1] = temp ;//till here
			}
		}
	}

	printf ( "\n\nArray after sorting:\n") ;

	for ( i = 0 ; i <= 4 ; i++ )
		printf ( "%d\t", arr[i] ) ;

}

Insertion sort needs two nested loops. k is assigned between the first for loop, and the second loop (a while loop usually).

I've never seen k (sometimes called key), value handled with an inner loop like that, and I very much doubt that it's a good idea to have a third nested loop, inside a sort function.

It's bumping the values down by one index, but that's not a good implementation, imo. Have you tested it and compared it with other Insertion sort codes? Before I could say anything else about it, I'd have to test it - it's just too easy to overlook something that changes the whole aspect of a sorting algorithm performance.

For instance, Insertion sort is one of the slower sort algorithms, BUT on small partly sorted arrays, it's blindingly fast - faster than Quicksort. In fact, I use it for that, to improve Quicksort, which it does very nicely - but only on smaller and/or, partly sorted arrays. (Which Quicksort produces, and then are passed over to Insertion sort, to finish up).