8 Replies - 2409 Views - Last Post: 02 September 2013 - 07:24 AM Rate Topic: -----

#1 Sawamura  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 01-September 12

Sorting Linked list with insertion sort

Posted 01 September 2013 - 08:39 AM

This is my sort my function and I am trying to implement an Insertion sort however every time I try to run the function it just hangs and doesn't do anything else. What am I doing wrong with my sorting ?
void SortData(Node *&head)
{

     int order;

     int  tempid,tempbookisbn,tempbookAmount;
     string tempname, tempbookname,tempbookauthor;

  cout<<"Choose the order the value is to be sorted (DES/ASSEN)  1 for Descending or 2 for Ascending:";
  cin>>order;

     Node* current1;
     Node* current2;
     current1=current2=head;


     if(head==NULL)              //checking that linked list have nodes or
      {
       cout<<"\n\n\n\t\tSORRY! there is no node in the linked list"<<endl;
      }//ending if

     else
     {
      if(order==1)
      {
       while(current1!=NULL)
        {
        while(current2->next!=NULL)                //check if node2 is not null
	    {
	     if(current2->id > current2->next->id)
	       {
            tempid=current2->id;
            current2->id=current2->next->id;
            current2->next->id=tempid;

            tempname=current2->name ;
            current2->name =current2->next->name ;
            current2->next->name=tempname;

            tempbookisbn=current2->bookisbn;
            current2->bookisbn=current2->next->bookisbn;
            current2->next->bookisbn=tempbookisbn;

             tempbookname=current2->bookname;
            current2->bookname=current2->next->bookname;
            current2->next->bookname=tempbookname;

            tempbookauthor=current2->bookauthor;
            current2->bookauthor=current2->next->bookauthor;
            current2->next->bookauthor=tempbookauthor;


            tempbookAmount=current2->bookAmount;
            current2->bookAmount=current2->next->bookAmount;
            current2->next->bookAmount=tempbookAmount;

	       }//
	     current2=current2->next;
	    }
	  current2= head;
	  current1=current1->next;
	 }//ending outer while
      }//ending if(order==DES)

        else if(order==2)
        {
       while(current1!=NULL)
        {
        while(current2->next!=NULL)                
	    {
	     if(current2->id < current2->next->id)
	       {


	           tempid=current2->id;
            current2->id=current2->next->id;
            current2->next->id=tempid;

            tempname=current2->name ;
            current2->name =current2->next->name ;
            current2->next->name=tempname;

            tempbookisbn=current2->bookisbn;
            current2->bookisbn=current2->next->bookisbn;
            current2->next->bookisbn=tempbookisbn;

             tempbookname=current2->bookname;
            current2->bookname=current2->next->bookname;
            current2->next->bookname=tempbookname;

            tempbookauthor=current2->bookauthor;
            current2->bookauthor=current2->next->bookauthor;
            current2->next->bookauthor=tempbookauthor;


            tempbookAmount=current2->bookAmount;
            current2->bookAmount=current2->next->bookAmount;
            current2->next->bookAmount=tempbookAmount;

           

	       }//
	     current2=current2->next;
	    }
	  current2=head;
	  current1=current1->next;
	 }//ending outer while
      }
      cout<<"\n\n\n\t\t\tNodes have been sorted.";
     }//ending else


}




Is This A Good Question/Topic? 0
  • +

Replies To: Sorting Linked list with insertion sort

#2 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3001
  • View blog
  • Posts: 10,393
  • Joined: 08-August 08

Re: Sorting Linked list with insertion sort

Posted 01 September 2013 - 08:53 AM

I don't think you're understanding the purpose of pointers. You don't need to copy data from one object to another. You only want to change the pointer values. That's the upside of pointers: they allow you to have large, complex objects without needing to move them around.
Was This Post Helpful? 0
  • +
  • -

#3 Sawamura  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 01-September 12

Re: Sorting Linked list with insertion sort

Posted 01 September 2013 - 09:32 AM

View PostCTphpnwb, on 01 September 2013 - 08:53 AM, said:

I don't think you're understanding the purpose of pointers. You don't need to copy data from one object to another. You only want to change the pointer values. That's the upside of pointers: they allow you to have large, complex objects without needing to move them around.


Sir I don't quite understand what you meant by not copying data from another and just change the pointer values. I am really a beginner in using linked list and currently just following tutorials on sorting functions. How can I change the pointer values without copying the data ?
Was This Post Helpful? 0
  • +
  • -

#4 Java Student  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 21
  • View blog
  • Posts: 481
  • Joined: 05-February 10

Re: Sorting Linked list with insertion sort

Posted 01 September 2013 - 09:42 AM

http://www.cplusplus...orial/pointers/

Try this link, it might be helpful to have a conceptual understanding of what pointers are in memory in order to see that they "point" to memory(variables) when you assign them, not copy them like primitive data types.

ie:
Copies:
int i=0;
i=2;//copied over 0



Pointers:
int k=1;
int* i=&k;//i holds a "pointer" to k in memory

//if i wanted to get back what i points to in memory
int j=*i;//copies what is pointed to by i


This post has been edited by Java Student: 01 September 2013 - 09:44 AM

Was This Post Helpful? 1
  • +
  • -

#5 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3001
  • View blog
  • Posts: 10,393
  • Joined: 08-August 08

Re: Sorting Linked list with insertion sort

Posted 01 September 2013 - 10:24 AM

Suppose you have a list of items:
Pointer	|	Address in list	|	Name	|	Phone	|	Street address
1	|	00001	|	Jim	|	888-555-1212	|	111 Main Street
2	|	00002	|	Alice	|	888-555-2112	|	333 Broad Steet

You want to sort them, but moving things around takes time and energy that are at a premium. If you move the name, phone, and street address it will be too slow/costly, but if you move the pointer value it will be very cheap:
Pointer	|	Address in list	|	Name	|	Phone	|	Street address
2	|	00001	|	Jim	|	888-555-1212	|	111 Main Street
1	|	00002	|	Alice	|	888-555-2112	|	333 Broad Steet

Now when you go through the list of pointers they point to items in alphabetical order by Name.
Note that with a list of two items the difference in cost doesn't matter much, but when the list is longer and the items contain more information the difference becomes very important.

This post has been edited by CTphpnwb: 01 September 2013 - 10:26 AM

Was This Post Helpful? 1
  • +
  • -

#6 Sawamura  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 01-September 12

Re: Sorting Linked list with insertion sort

Posted 01 September 2013 - 06:20 PM

Node * a = head
Node *b = head->next

swap function(node a,node B)
{
a = b ;
b = a ;

}

will it look something like this ?
Was This Post Helpful? 0
  • +
  • -

#7 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3001
  • View blog
  • Posts: 10,393
  • Joined: 08-August 08

Re: Sorting Linked list with insertion sort

Posted 01 September 2013 - 06:30 PM

Something like it. The problem is that once you set a = b you cannot set b = a because it will remain its current value ( a is already b ). You'll need a temporary address. Note that your function should be receiving pointers: Node *a

This post has been edited by CTphpnwb: 01 September 2013 - 06:30 PM

Was This Post Helpful? 0
  • +
  • -

#8 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3589
  • View blog
  • Posts: 11,164
  • Joined: 05-May 12

Re: Sorting Linked list with insertion sort

Posted 01 September 2013 - 09:08 PM

Since the OP is using C++, why can't she/he use std::swap() ?
Was This Post Helpful? 1
  • +
  • -

#9 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3001
  • View blog
  • Posts: 10,393
  • Joined: 08-August 08

Re: Sorting Linked list with insertion sort

Posted 02 September 2013 - 07:24 AM

I think the answer is because the OP is learning C++. After learning to write a swap function it's ok to use the STL. ;)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1