1,105,384 Community Members

Selection Sort 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
 

Hello again, I am asked by my professor to create a program using selection sort in a linked list. Selection sort with sorting only the data is pretty easy, but I'm having a hard time because he made us sort the nodes themselves. Can anyone help by giving atleast the algorithm in sorting the nodes. Thank you. Here is my code so far, it's only about sorting the data:

#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();
    Sort();
    cout << "\nDisplay after sorting.\n";
    Display();
}

void Sort()
{
    node *h = HEAD, *i, *j, *next_i;
    for(i = h; i!=NULL && i->NEXT!=NULL; i=i->NEXT)
    {
        node *min;
        min = i;
        for(j = i->NEXT; j!=NULL ; j=j->NEXT)
        {
            if(j->DATA < min->DATA)
                min=j;
        }
        if(min!=i)
        {
            int temp;
            temp = min->DATA;
            min->DATA = i->DATA;
            i->DATA = temp;
        }
    }
    HEAD = h;
}

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;
    }
}
Member Avatar
Ancient Dragon
Achieved Level 70
27,632 posts since Aug 2005
Reputation Points: 5,232 [?]
Q&As Helped to Solve: 3,037 [?]
Skill Endorsements: 115 [?]
Team Colleague
Featured
Sponsor
 
0
 

Your program worked perfectly for me using VC++ 2010 Express on Windows 7. since this is c++ code you don't need the typedef symbol.

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

Yes, it works. But it only swaps the data. I have to make it swap the nodes themselves.

Member Avatar
mike_2000_17
21st Century Viking
4,081 posts since Jul 2010
Reputation Points: 2,253 [?]
Q&As Helped to Solve: 800 [?]
Skill Endorsements: 73 [?]
Moderator
Featured
Sponsor
 
0
 

Forgive AD, he's getting a bit senile ;)

From your last thread, you do know how to swap two nodes that are next to each other, right? Well, you should, because I told you how.

The problem with swapping two adjacent nodes is that you also needed to keep track of the node before that pair of nodes such that you could update its NEXT pointer. Here, you have the same problem, but twice. If you want to swap two nodes that are possibly far from each other in the list, you need to keep track of the nodes that preceed both nodes that you are about to swap. In other words, you would need node* before_i; and node* before_min;.

To keep track of those nodes is not hard, this would do the trick for before_min:

node* min = i;
node* before_min = NULL;
for(node* j = i; j->NEXT != NULL; j = j->NEXT) {
  if( j->NEXT->DATA < min->DATA ) {
    before_min = j;
    min = j->NEXT;
  };
};

and you can do something similar for the outer loop.

After the inner-loop, if before_min is still NULL, then you don't have to swap anything.

Then, for the actual swap, you have to check if i is the HEAD node in which case it has to predecessor to update, but the value of HEAD has to be changed to the new node that will become the head. If i is not the head and i != min, then you swap them by updating the NEXT pointer in each other's predecessors and by swapping their own NEXT pointers. The only other sticky point to consider is when before_min == i, but this means that i and min are adjacent nodes, so, you can use the same swapping method as in the bubble-sort you had before.

BTW, let me guess that insertion-sort will be your next assignment!

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

Thank you again! Hah, I really hope not.

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

I'm sorry, Mike. But I guess I just don't quite get it. Think of me as a 17 year old kid trying to figure this out which is true. So anyway, I got lost with me checking if i is the HEAD node in which case it has to predecessor to update. What do you mean by that? Thank you! Here's my disaster of a code of my sort so far:

void Sort()
{
    node *h = HEAD, *i, *next_i;
    for(i = h; i!=NULL && i->NEXT!=NULL; i=i->NEXT)
    {
        node *min;
        min = i;
        node *before_min = NULL;
        for(node *j = i->NEXT; j->NEXT!=NULL ; j=j->NEXT)
        {
            if(j->DATA < min->DATA)
            {
                before_min=j;
                min=j;
            }
        }
        if(before_min == NULL)
            return;
        else if(i == HEAD)
        {

        }
        else if(before_min == i)
        {
            i = min->NEXT;
            min->NEXT = i->NEXT;
            i->NEXT = min;
            if(min == HEAD)
            {
                HEAD = i;
                min = i;
            }
            else
            {
                min = i;
            }
        }
    }
    HEAD = h;
}
Member Avatar
mike_2000_17
21st Century Viking
4,081 posts since Jul 2010
Reputation Points: 2,253 [?]
Q&As Helped to Solve: 800 [?]
Skill Endorsements: 73 [?]
Moderator
Featured
Sponsor
 
0
 

You should use exactly the inner loop that I posted before, yours is incorrect.

About this: "in which case it has to predecessor to update", it was a typo, I meant to write "in which case it has NO predecessor to update". I think that makes more sense, doesn't it?

Your outer loop should probably start in a fashion like this:

node* before_i = NULL;
for(node* i = HEAD; i->NEXT != NULL; i = i->NEXT) {

  //.. the code..

  //.. at the end of the iteration:
  before_i = i;
};

This will make sure that you keep track of the node that comes before i.

Then, the swapping (after the inner-loop), should have this kind of structure of if-statements:

if( before_min != NULL ) {   // if a swap is required.

  if( i == before_min ) {   // if i comes just before the min node.

    if( i == HEAD ) {    // if i is at the head, it has no predecessor, but HEAD needs to be updated.

      // put min at the head, and order the next pointers such that min --> i --> (min->NEXT)

    } else {             // otherwise, there is at least one node before i (i.e. before_i != NULL).

      // swap the nodes as you did before in the bubble-sort algorithm (swap nodes i and min, with before_i being their predecessor).

    };
  } else {                  // otherwise, i and min are separated by at least one node.

    if( i == HEAD ) {    // if i is at the head, it has no predecessor, but HEAD needs to be updated.

      // update the HEAD pointer to point to min, and place i next to before_min, and then swap the NEXT pointer in i and min.

    } else {             // otherwise, there is at least one node before i (i.e. before_i != NULL).

      // swap the NEXT pointers in before_i and before_min, and swap the NEXT pointers in i and min.

    };
  };
};

Now, all you need to do is implement those instructions. I cannot make it any clearer than that without doing it all for you.

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: