Insertion sort

This is a discussion on Insertion sort within the C++ Programming forums, part of the General Programming Boards category; Code: void insertionSort() { node* temp=head; while(temp->next != NULL) { node* second =temp->next; if (second->exponent==temp->exponent) { temp=temp->next; } else { ...

  1. #1
    Registered User
    Join Date
    Mar 2009
    Posts
    112

    Insertion sort

    Code:
    void insertionSort()
    	{
    		node* temp=head;	
    		
    		while(temp->next != NULL)
    		{
    			node* second =temp->next;
    			if (second->exponent==temp->exponent)
    			{
    				temp=temp->next;
    			}
    			else
    			{
    				second->previous->next=second->next;
    				second->next->previous=second->previous;
    				
    				if (head->exponent > second->exponent)
    				{
    					second->next=head;
    					second->previous=NULL;
    					head->previous=second;
    					head= second;
    				}
    				node* current = head->next;
    			
    				while(current->exponent < second->exponent)
    				{
    					current=current->next;
    				}
    				second->next=current;
    				second->previous=current->previous;
    				current->previous->next=second;
    				current->previous=second;
    			}
    		}
    	}
    I have made insertion sort funtion for a doubly linked list , but its not working , i cant figure out the errors.If anybody can guide a bit. =|

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Perhaps you've overcomplicated it. You could ignore the case where an item is greater than all items inserted thus far:
    Code:
    template <class TItem>
    void InsertionSort(TItem *&head) {
    	TItem *newList = NULL, *oldList = head;
    	while (oldList != NULL) {
    		//take an item off the old list
    		TItem *temp = oldList;
    		oldList = oldList->next;
    		TItem *curr = newList, *prev = NULL;
    
    		//find the place in the new list for this item
    		while (curr != NULL) {
    			if (*temp < *curr)
    				break;
    			prev = curr;
    			curr = curr->next;
    		}
    		//put the item in the new list
    		if (prev == NULL)
    			newList = temp;
    		else
    			prev->next = temp;
    		temp->next = curr;
    	}
    	head = newList;
    }
    Sure that's slower for an already sorted list, but we're not using InsertionSort for sorting long lists anyway, if we know what's good for us.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Mar 2009
    Posts
    112
    I dun know how to work with the templates i would be thankful, if u point out where my code needs to changed i would be thnakful.

  4. #4
    Registered User
    Join Date
    Mar 2009
    Posts
    112
    I have made a doubly linked list of polynomials and now i am using operator overloading to add two polynomials. The add function see its the exponents of the two polynomials are same and then add them. It returns the only node after addition whose addition is being done, but i want to get the whole list of polynomials , whether they are added or not.
    e.g
    1x^1 2x^2 when added with 1x^1 3x^6
    gives
    2x^1 2x^2 3x^6
    So kindly tell how to insert the terms (those whose exponents dont match) to the result list.


    Code:
    	list operator + (const list& k)
    	{
    		node* first;
    		first = head;
    		node* second;
    		second = k.head;
    		
    		node* result=head;
    		list r;
    		
    		while (first != NULL)
    		{
    			while (second != NULL)
    			{
    				if (first->exponent == second->exponent )
    				{
    					
    					result->coefficient	=first->coefficient + second->coefficient;
    					result->exponent=first->exponent;
    					
    				}
    				second=second->next;
    			}
    			first=first->next;
    		}
    		r.insert(result->coefficient,result->exponent);
    		return r;
    	}

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Quote Originally Posted by Fatima Rizwan View Post
    I dun know how to work with the templates i would be thankful, if u point out where my code needs to changed i would be thnakful.
    Just ignore that first line and call it with any type you like that has a member called 'next'.

    Okay so the code I posted was for a singly-linked list, but it's easy enough to add a few more lines to hook up the links in the opposite direction.

    The thing about your code is that it's uncommented and not easy to understand. To be honest, there is no one-line change to make that fixes it. Even this line:
    Code:
    while(temp->next != NULL)
    is wrong because it will crash when head is NULL.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Mar 2009
    Posts
    112
    Ok thnks . And what about the second problem
    Code:
    if (first->exponent == second->exponent )
    				{
    					result->coefficient	=first->coefficient - second->coefficient;
    					result->exponent=first->exponent;
    					r.insert(result->coefficient,result->exponent);
                      // AFTER INSERTION I WANT TO DELETE THE NODE OF FIRST AND SECOND whose exponent are same, but m having problem with this. 
    				
    				}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 01-26-2010, 08:02 AM
  2. Replies: 5
    Last Post: 08-02-2008, 06:23 AM
  3. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  4. Insertion Sort on Array of Structs
    By n0r3gr3tz in forum C Programming
    Replies: 3
    Last Post: 04-01-2008, 08:28 AM
  5. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM

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