netonotisr inor (insertion sort)

This is a discussion on netonotisr inor (insertion sort) within the C++ Programming forums, part of the General Programming Boards category; Trying to come up with a good algorithm for an insertions sort.. singly linked list.. Function will accept the head ...

  1. #1
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903

    netonotisr inor (insertion sort)

    Trying to come up with a good algorithm for an insertions sort.. singly linked list..

    Function will accept the head node to a list.. locate the highest and second highest nodes of a list (in this case based on the "priority" attribute.) Just want to know from people who have already ventured into this realm if I am on the road to success... Kinda having second thoughts on how to perform the actual swapping of nodes..

    Code:
    //Insertion Sort
    void priority_sort(Node* head_ptr)
    {
    	Node *higher, *lower, *current, *temp;	
    	unsigned int elimination;
    	bool sorted = true;
    
    	temp = head_ptr;
    
    	if(head_ptr && head_ptr->next)
    	{
    		//Test for Sorted (Ascending Order)
    		while(temp && sorted)
    		{
    			current = temp;
    			temp = temp->next;
    
    			if(current->priority > temp->priority)
    
    				sorted = false;
    		}
    
    		if(!sorted)
    		{
    			current = head_ptr;
    			temp	= head_ptr->next;
    			higher  = NULL;
    
    			//Locate Highest & 2nd Highest 
    			while(temp)
    			{				
    				lower   = NULL;
    
    				if(current->priority > temp->priority && temp->priority < elimination)
    					
    					if(higher)
    					
    						lower = higher;
    					
    					higher = current;
    
    				elimination = lower->priority;
    			}
    			
    			//Swap Highest and 2nd Highest Nodes
    			if(lower)
    			{		
    				temp   = lower;
    				higher = lower;
    				lower  = temp;
    			}
    
    			//Handle case of last iteration
    			if(!lower && higher)
    			{
    				temp = head_ptr;
    				head_ptr = higher;
    				higher = temp;
    			}
    		}
    	}
    }
    Last edited by The Brain; 05-04-2005 at 04:17 PM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 05:03 AM
  2. threaded merge sort
    By AusTex in forum Linux Programming
    Replies: 4
    Last Post: 05-04-2005, 05:03 AM
  3. Sorting
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 11-10-2003, 05:21 PM
  4. radix sort and radix exchange sort.
    By whatman in forum C Programming
    Replies: 1
    Last Post: 07-31-2003, 01:24 PM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM

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