Thread: Insertion sort - sort an array of structs using a single field

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    74

    Insertion sort - sort an array of structs using a single field

    I have an array of structs
    Code:
    typedef struct node
    {
    	int a,b,c,d;	
    } element;
    
    ...
    
    	element array[5];
    i want to compare the field a
    Code:
    if (niz[j].a > niz[j+1].a)
    but swap the entire element.

    basiccaly doing what excel does, when you sort one column which is asociated with other columns.

    i.e.

    Code:
    PRE SORT
    =========
    
    20	14	32
    13	21	26
    19	17	11
    
    POST SORT
    =========
    
    13	21	26
    19	17	11
    20	14	32
    the problem is, i don't know how to do it with insertion sort. this is my insertion sort which works on a "normal" 1D int array but I need to modify it

    Code:
    void Insertion (int array[], int n)
    {
    	int i;
    
    	for (i=0; i < n; i++)
    	{
    		int j, temp = array[i];
    		 
    		for (j = i - 1; j >= 0; j--)
    		{
    			if (array[j] <= v) break;
    			array[j + 1] = array[j];
    		}
    	  
    		array[j + 1] = temp;
    		 
    	}
    	
    }

  2. #2
    Registered User
    Join Date
    Apr 2009
    Posts
    74
    solved it. trivial really but not a couple of hours ago

    one simply needs to keep track of the element from which we are using the desired field for comparison. I called it element x

    Code:
    int i;
    	element x;
    
    	for (i=0; i < n; i++)
    	{
    		int j, v = array[i].a;
    		x = array[i];
    		 
    		for (j = i - 1; j >= 0; j--)
    		{
    			if (array[j].a >= v) break;
    			array[j + 1] = array[j];
    			
    		}
    	  
    		array[j + 1].a = v;
    		array[j + 1] = x;		 
    	}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 04:15 AM
  3. Inserting new member into array of structs
    By cathym in forum C Programming
    Replies: 6
    Last Post: 04-17-2005, 07:10 AM
  4. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 09:54 AM
  5. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 09:48 AM

Tags for this Thread