Can anybody tell me what's wrong with my selection sort of linked lists? It's meant to sort the whole node, not 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 *before_i = NULL; node *i = HEAD;
    while(i->NEXT != NULL)
    {
        node *min = i;
        node *before_min = NULL;
        node *j = i;
        while(j->NEXT != NULL)
        {
            if(j->NEXT->DATA < min->DATA)
            {
                before_min = j;
                min = j->NEXT;
            }
            j = j->NEXT;
        }
        if( before_min != NULL ) 
        {
             if( i == before_min ) 
             {   
                    if( i == HEAD ) 
                    {   
                        HEAD = min;
                        if(min->NEXT != NULL)
                            i->NEXT = min->NEXT;
                        else
                            i->NEXT = NULL;
                        min->NEXT = i;
                    }
                    else 
                    {            
                        before_i->NEXT = min;
                        min = i->NEXT;
                        i->NEXT = min->NEXT;
                        min->NEXT = i;
                        i = min;
                    }
                } 
             else 
             {                  
                 if( i == HEAD ) 
                    {    
                        if(min->NEXT != NULL)
                            before_min->NEXT = min->NEXT;
                        else
                            before_min->NEXT = NULL;
                        HEAD = min;
                        min->NEXT = i;
                    } 
                 else 
                 {             
                     if(min->NEXT != NULL)
                        before_min->NEXT = min->NEXT;
                     else
                         before_min->NEXT = NULL;
                     before_i->NEXT = min;
                     min->NEXT = i->NEXT;
                 }
             }
        }
        before_i = i;
        if(i->NEXT != NULL)
            i = i->NEXT;

    }
}

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

Its taking a while to understand how you are doing it. So, I wrote it my way. The first thing I do see is that you are not swapping the min value with the head.

http://en.wikipedia.org/wiki/Selection_sort

  1. Find the minimum value in the list
  2. **Swap** it with the value in the first position
  3. Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)

Notice the difference between my version and yours. I called Display before the i = i->NEXT.

Your version

$ ./a.out
Enter number of elements: 4
Enter 4 numbers: 4
3
2
1

Display before sorting.
                LAST              NUMBER                NEXT
         0x100100080                   4         0x100100090
         0x100100090                   3         0x1001000a0
         0x1001000a0                   2         0x1001000b0
         0x1001000b0                   1                   0

                LAST              NUMBER                NEXT
         0x1001000b0                   1         0x100100080  <--- 1 is right 
         0x100100080                   4         0x100100090  <--- 4 is not right
         0x100100090                   3         0x1001000a0
         0x1001000a0                   2                   0  <--- 4 should be here

                LAST              NUMBER                NEXT
         0x1001000b0                   1         0x100100080
         0x100100080                   4         0x1001000a0
         0x1001000a0                   2         0x100100090
         0x100100090                   3                   0

Display after sorting.
                LAST              NUMBER                NEXT
         0x1001000b0                   1         0x100100080
         0x100100080                   4         0x1001000a0
         0x1001000a0                   2         0x100100090
         0x100100090                   3                   0
$

My version

$ ./a.out
Enter number of elements: 4
Enter 4 numbers: 4
3
2
1

Display before sorting.
                LAST              NUMBER                NEXT
         0x100100080                   4         0x100100090
         0x100100090                   3         0x1001000a0
         0x1001000a0                   2         0x1001000b0
         0x1001000b0                   1                   0
                LAST              NUMBER                NEXT
         0x1001000b0                   1         0x100100090  <-- 1 & 4 have swapped 
         0x100100090                   3         0x1001000a0  
         0x1001000a0                   2         0x100100080
         0x100100080                   4                   0  <-- 4 is now in place of the min
                LAST              NUMBER                NEXT
         0x1001000b0                   1         0x1001000a0
         0x1001000a0                   2         0x100100090
         0x100100090                   3         0x100100080
         0x100100080                   4                   0
                LAST              NUMBER                NEXT
         0x1001000b0                   1         0x1001000a0
         0x1001000a0                   2         0x100100090
         0x100100090                   3         0x100100080
         0x100100080                   4                   0

Display after sorting.
                LAST              NUMBER                NEXT
         0x1001000b0                   1         0x1001000a0
         0x1001000a0                   2         0x100100090
         0x100100090                   3         0x100100080
         0x100100080                   4                   0
$ 

Still trying to map what I did to what you did so I can see where you code goes wrong.

Edited 4 Years Ago by histrungalot: Format

How you are moving through the list is not correct. You are skipping nodes. I put some debug in to see what is going on.

$ ./a.out
Enter number of elements: 4
Enter 4 numbers: 4
3
2
1

Display before sorting.
                LAST              NUMBER                NEXT
         0x100100080                   4         0x100100090
         0x100100090                   3         0x1001000a0
         0x1001000a0                   2         0x1001000b0
         0x1001000b0                   1                   0
Top of while i->DATA(4)  <-------------------------------------- Correct
                LAST              NUMBER                NEXT
         0x1001000b0                   1         0x100100080
         0x100100080                   4         0x100100090
         0x100100090                   3         0x1001000a0
         0x1001000a0                   2                   0
Top of while i->DATA(3)  <-------------------------------------- Not Correct
                LAST              NUMBER                NEXT
         0x1001000b0                   1         0x100100080
         0x100100080                   4         0x1001000a0
         0x1001000a0                   2         0x100100090
         0x100100090                   3                   0

Display after sorting.
                LAST              NUMBER                NEXT
         0x1001000b0                   1         0x100100080
         0x100100080                   4         0x1001000a0
         0x1001000a0                   2         0x100100090
         0x100100090                   3                   0
$

See how the fist time the data value for i->DATA is 4. Correct. The next time the value of i->DATA is 3. Not correct. The value should be 3.You hit the end before you have checked all of the values in the list.

Edited 4 Years Ago by histrungalot: Format

A lot of things are wrong with your code.

First of all, you have things that are just useless, like these types of things:

                    if(min->NEXT != NULL)
                        i->NEXT = min->NEXT;
                    else
                        i->NEXT = NULL;

Tell me how that is different from this:

                    i->NEXT = min->NEXT;

??? (rhetorical)

Second, your code to do the swapping is not correct, it is a weird and incomplete mix of extraction and insertion with something else. I get the strong feeling you just copied code that does an extraction-and-insertion into that loop as if it does the same as swapping, without putting any more thoughts of your own into it. I know, you PMed me about insertion-sort, and I gave you an illustrative example of code to do extraction and insertion, and you copied it into your selection-sort algorithm. I'm trying to detect the presence of an intelligent life-form behind your user account, one who can understand the difference between illustrating an idea and writing real code, between insertion and swapping, one who can think for himself and develop an understanding of the problem and construct a path to a solution. Histrungalot is showing you how to solve a problem, by outputting the intermediate steps and figuring out what is happening versus what should happen (from the theoretical algorithm).

Start by going step by step, with pen and paper, through your algorithm, with the aid of the print-out that histrungalot has posted and figure out exactly what is happening. I ask you to put comments, at each line, telling, in your words, what that line is doing. Also, at every "swapping" piece of code, figure out what is the state of your linked-list and what are the values of the pointers before_i, i, before_min and min, before AND after the "swap" has been done. Going through this method will show you what the problems are, guaranteed. I cannot post the solution to this, because you need to learn to find it on your own.

I think I managed to get it right this time, I only got the idea right when I was explaining it to my other classmate on how to sort nodes using selection sort which is really ironic. Anyway here's my code.

void Sort()
{
    node *count = HEAD;
    int cnt = 0;
    while(count!=NULL)
    {
        cnt++;
        count = count->NEXT;
    }
    for(int z = 0 ; z < cnt-1 ; z++)
    {
        node *before_i = NULL; node *i = HEAD;
        while(i->NEXT != NULL)
        {
            node *min = i;
            node *before_min = NULL;
            node *j = i;
            while(j->NEXT != NULL)
            {
                if(j->NEXT->DATA < min->DATA)
                {
                    before_min = j;
                    min = j->NEXT;
                }
                j = j->NEXT;
            }
            if( before_min != NULL ) 
            {
                 if( i == before_min ) 
                 {   
                        if( i == HEAD ) 
                        {   
                            HEAD = min;
                            i->NEXT = min->NEXT;
                            min->NEXT = i;
                        }
                        else 
                        {            
                            before_i->NEXT = min;
                            min = i->NEXT;
                            i->NEXT = min->NEXT;
                            min->NEXT = i;
                            i = min;
                        }
                    } 
                 else 
                 {                  
                     if( i == HEAD ) 
                        {    
                            HEAD = min;
                            before_min->NEXT = i;
                            node *temp = new node;
                            temp->NEXT = i->NEXT;
                            i->NEXT = min->NEXT;
                            min->NEXT = temp->NEXT;
                            i = HEAD;
                            free(temp);
                        } 
                     else 
                     {             
                         node *temp = new node;
                         temp->NEXT = before_i->NEXT;
                         before_i->NEXT = before_min->NEXT;
                         before_min->NEXT = temp->NEXT;
                         temp->NEXT = i->NEXT;
                         i->NEXT = min->NEXT;
                         min->NEXT = temp->NEXT;
                         i = HEAD;
                         free(temp);
                     }
                 }
            }
            before_i = i;
            if(i->NEXT != NULL)
                i = i->NEXT;
        }
    }
}

Edited 4 Years Ago by cryonize: Forgot a few lines.

You're using new with free, which is a no-no. New-delete or malloc-free. At first glance it also appears that your code is over complicated. Why are you creating so much temporary objects when you're just going to delete them 3 lines later? Swapping pointers will do just fine.

Edited 4 Years Ago by Nick Evan: typo

This article has been dead for over six months. Start a new discussion instead.