Insertion Sort

This is a discussion on Insertion Sort within the C Programming forums, part of the General Programming Boards category; I stared the code for hours and still can't figure out what's the meaning of the following line of code. ...

  1. #1
    Registered User
    Join Date
    Aug 2011
    Posts
    102

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

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Insertion sort
    By UserName112 in forum C++ Programming
    Replies: 2
    Last Post: 10-11-2011, 04:47 AM
  2. Insertion sort
    By Fatima Rizwan in forum C++ Programming
    Replies: 5
    Last Post: 02-26-2010, 02:24 PM
  3. Replies: 1
    Last Post: 01-26-2010, 09:02 AM
  4. Insertion Sort Help
    By Odinwar in forum C++ Programming
    Replies: 8
    Last Post: 12-09-2009, 11:27 AM
  5. Insertion Sort Help
    By vgame64 in forum C++ Programming
    Replies: 2
    Last Post: 09-08-2006, 08:54 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21