1,105,340 Community Members

Insertion Sort Singly-Linked List

Member Avatar
cryonize
Newbie Poster
12 posts since Mar 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

I have a bit a of a problem because I have no idea what's going on in my code. Could someone guide me with this? **It has to swap the nodes themselves.
**

#include <iostream>
#include <iomanip>
using namespace std;

typedef struct node
{
    int DATA;
    node *NEXT;
};

node *HEAD = NULL;
void Create(int data);
void Display();
void Sort();

int main()
{
    int num, numOfEl;
    cout << "Enter number of elements: ";
    cin >> numOfEl;
    cout << "Enter " << numOfEl << " numbers: ";
    for(int i = 0 ; i < numOfEl ; i++)
    {
        cin >> num;
        Create(num);
    }
    cout << "\nDisplay before sorting.\n";
    Display();
    node *before_i = NULL; node *i = HEAD;
    while(i->NEXT != NULL)
    {
        node *before_j = NULL;
        node *j = i;
        while(j->NEXT!=NULL)
        {
            before_j = j;
            j = j->NEXT;
            if(j->DATA > i->DATA)
                break;
        }
        if(before_j!= NULL)
        {
            if(i == HEAD)
            {
                HEAD = j;
                before_j->NEXT = j->NEXT;
                j->NEXT = i;
            }
            else
            {
                before_i->NEXT = j;
                before_j->NEXT = j->NEXT;
                j->NEXT = i;
            }
        }
        before_i = i;
        Display();
        if(i->NEXT != NULL)
            i = i->NEXT;
    }
    //Sort();
    cout << "\nDisplay after sorting.\n";
    Display();
}

void Sort()
{
    node *k, *nwlist;
    nwlist = HEAD; k = HEAD->NEXT ;
    while(k != NULL)
    {
        Display();
        node *ptr;
        if(nwlist->DATA > k->DATA)
        {
            node *tmp;
            HEAD = k;
            k = k->NEXT;
            HEAD->NEXT = nwlist;
            nwlist->NEXT = k;
            continue;
        }
        for(ptr = nwlist ; ptr->NEXT != NULL ; ptr = ptr->NEXT)
        {
            if(ptr->NEXT->DATA > k->DATA)
                break;
        }
        if(ptr->NEXT!=NULL)
        {
            node *tmp;
            tmp = k ;
            k = k->NEXT;
            ptr->NEXT = tmp->NEXT;
            tmp->NEXT = ptr;
            continue;
        }
        if(ptr->NEXT == NULL)
        {
            ptr->NEXT = k;
            k = k->NEXT;
            ptr->NEXT->NEXT = NULL;
            continue;
        }

    }
}


void Display()
{
    node *current;
    current = HEAD;
    cout << setw(20) << "LAST" << setw(20) << "NUMBER" << setw(20) << "NEXT" << endl;
    while(current != NULL)
    {
        cout << setw(20) << current << setw(20) << current->DATA << setw(20) << current->NEXT << endl;
        current = current->NEXT;
    }
    system("pause>0");
}

void Create(int data)
{
    node *front, *tail;
    tail = new node;
    tail->DATA = data;
    tail->NEXT = NULL;
    if(HEAD == NULL)
        HEAD = tail;
    else
    {
        front = HEAD;
        while(front->NEXT!=NULL)
            front = front->NEXT;
        front->NEXT = tail;
    }
}
doomilator
Newbie Poster
1 post since Apr 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
Unverified Member
 
0
 

first, I would not recommend doing this in main. Create a class called List, or whatever you would like to call it.
Second, please comment your code as it is very confusing.
Third, your Create should look different.

void create(int data){
    node *ptr;
    ptr = new node;
    ptr->data = data;
    if(HEAD == NULL){
        HEAD = ptr;
    }
    else{
        //keep going to the next spot in
        //the list until it is equal to NULL
        // then insert
    }
}

that is an incomplete function but it should give you a clearer idea of what to do.

Member Avatar
raptr_dflo
Practically a Master Poster
604 posts since Aug 2010
Reputation Points: 48 [?]
Q&As Helped to Solve: 83 [?]
Skill Endorsements: 1 [?]
 
0
 

Your sorting code in main() looks close, but as doomilator suggests, move it into the Sort() routine.
Then initialize j = i->NEXT and loop while j != NULL (otherwise you're needlessly comparing i to itself the first time, and never checking the last element in the list). Also, your comparison direction might be wrong at line 38. And you're swapping the first out-of-order element you find, but there might be a better one further on, so you have to check all of the j's before advancing i. Then double check that the right thing happens if you're swapping adjacent nodes (where before_j == i), though it might already be ok, just double-check. Finally, make sure you handle the degenerate cases where there are zero or one nodes in your list.

Good luck, and post back just your sort routine (if that's all that's broken) if you get stuck again. :)

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: