Selection Sort Linked List

[cryonize]

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;
    }
}

[Ancient Dragon]

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.

[cryonize]

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

[mike_2000_17]

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!

[cryonize]

Thank you again! Hah, I really hope not.

[cryonize]

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;
}

[mike_2000_17]

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.