Thread: netonotisr inor (insertion sort)

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

    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..

    //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;
    			current = head_ptr;
    			temp	= head_ptr->next;
    			higher  = NULL;
    			//Locate Highest & 2nd Highest 
    				lower   = NULL;
    				if(current->priority > temp->priority && temp->priority < elimination)
    						lower = higher;
    					higher = current;
    				elimination = lower->priority;
    			//Swap Highest and 2nd Highest Nodes
    				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 03: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, 04:03 AM
  2. threaded merge sort
    By AusTex in forum Linux Programming
    Replies: 4
    Last Post: 05-04-2005, 04:03 AM
  3. Sorting
    By vasanth in forum A Brief History of
    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, 12: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