Insertion sort on singly link list

[ariel930]

Hi,I am having a hard time trying to do insertion sort on a singly link list containing single alphabets.I have spent hours doing this but still it wont work.Any help will be apprecited.

Here is my code:

# include <iostream>

using namespace std;

class node
{
public:

char info;
node *next;

node(char e1,node *ptr=0)
{
info=e1;
next=ptr;
}

};
 class linklist
 {
             private:
                     node *head;
             public:

                    linklist()
                    {
                    head=0;
                    }

                    void addtohead(char e1)
                    {
                    head=new node(e1,head);     
                    }


                    void Printlist()
                    { 
                         node *temp=head;
                         while(temp!=NULL)
                         {
                        cout<<temp->info<<endl;
                        temp=temp->next;


                        }
                    }
             void insertionsort()
             {
             node *i,*j;
             char min;

             for(i=head->next;i!=NULL ;i=i->next)
             {
              min=i->info;


             for(j=i->next;j!=NULL && j->info > min ;j=j->next)
             {
             i->info=j->info;
             j->info=min;

             }

             }

             }
};
int main()
{
    int count;
    char c;

    cout<<"How many nodes you want to create?"<<endl;
    cin>>count;

    linklist list;
    for(int i=0;i<count;i++)
    {
    cout<<"Enter node "<<i+1<<": "<<endl; 
    cin>>c;
    list.addtohead(c);      
    }

    list.insertionsort(count);
    cout<<"the sorted link list using insertion sort is:"<<endl;
    list.Printlist();

 system("pause");
 return 0;
}

[BobS0327]

The addtohead method isn't needed. Use the insertionsort method to add (insert) a char and sort the linked list.

You'll have to address four different cases in a insertion sort linked list:

Case 1. An inserted node is the first one to be added to an empty list.
Case 2. The inserted node’s key is less than those of all others in the list; thus, the node goes at the beginning of a nonempty list.
Case 3. The key is greater than all the others; thus, the node goes at the end of the list.
Case 4. The key lies between two others; thus, the node goes in the middle of the list somewhere.

[ariel930]

Now it works fine...thank you so much.

[hemalatha509]

can u please post the code changes that worked for insertion sort

[richieking]

for insrtion sort. you need to go like this.
psuedo.

void insertSorted( person *p){ //takes the node pointer person
        person * newNode =p;    // 
        person * curr = 0;     //  formality
        person *worker  = head; //

        if(head ==0){ // check if there's no node
            head = newNode;
            }
            else{   
                while(worker !=0){  // loop 

    if(worker ->data >= newNode->data){ // check for >=
            break;
        }
        else{
              curr = worker;
              worker->Next= worker;
                }
             }
        }

        if(newNode == head){  // then insert
        newNode->Next=head;
        head=newNode;
        }
        else{
           newNode->Next=worker;
           curr->Next= newNode; 

          }
        }

this is the idea mate. ))