linked list problem

[I_m_rude]

hi...

Can you please help me by giving only some HINTS of algorithm used to solve this. I AM NOT ASKING ANY CODE OR SNIPPET FROM ANYONE. I just want hint or algorithm to use...

There is a linked list where some nodes have similar number. Sort them such that all the similar number nodes are cluster together.

thanks in advance.

[Ancient Dragon]

use bubble sort algorithm (the easiest to code) and sort the list by number. When a swap is needed just swap the data within the node structure, not the nodes themselves.

[I_m_rude]

it is of high order i.e O(n^2). please give a low order algorithm. thanks.

[deceptikon]

If the length of your list is large enough that a faster sort is warranted, then a linked list is the wrong choice of data structure. But I'll mention two things:

1. Bubble sort is a bitch with linked lists. Insertion sort is much easier to implement.

2. Following that line of thought, any algorithm that can run with streamed data is well suited to linked lists, so my first suggestion of a faster sort would be merge sort.

[Ancient Dragon]

Bubble sort is a bitch with linked lists

Not really. See function Sort() in the code below

#include <iostream>
#include <cstdlib>
#include <ctime>

class Node
{
public:
    Node(int d) {setData(d); next = NULL;}
    int getData() {return data;}
    void setData(int d) {data = d;}
public:
    Node* next;
protected:
    int data;
};

const int MaxNodes = 10;

Node* GetTail(Node* head)
{
    if(head == NULL) return NULL;
    while( head->next )
        head = head->next;
    return head;
}

void ShowNodes(Node* head)
{
    while(head)
    {
        std::cout << head->getData() << '\n';
        head = head->next;
    }
    std::cout << "\n";
}

void InsertTail(Node**head, int d)
{
    Node* newnode = new Node(d);
    Node* n = GetTail(*head);
    if(n == NULL)
        *head = newnode;
    else
        n->next = newnode;

}

void Sort(Node* head)
{
    Node* t1, *t2;

    for(t1 = head; t1->next != NULL;t1 = t1->next)
    {
        for(t2 = t1->next;t2 != NULL; t2 = t2->next)
        {
            if( t1->getData() > t2->getData() ) 
            {
                int temp = t1->getData();
                t1->setData(t2->getData());
                t2->setData(temp);
            }
        }
    }
}


void FreeNodes(Node** head)
{
    Node* curr = *head;
    while(curr)
    {
        Node* n = curr;
        curr = curr->next;
        delete n;
    }
    *head = NULL;
}

int main()
{
    Node* head = 0;

    srand((unsigned int)time(0));
    for(int i = 0; i < MaxNodes; i++)
    {
        InsertTail(&head,rand());
    }

    ShowNodes(head);
    Sort(head);

    ShowNodes(head);

    FreeNodes(&head);



   return 0;
}

[deceptikon]

Not really. See function Sort() in the code below

I stand corrected. Bubblesort is still painfully inefficient though, and even more so with linked lists due to the excessive chasing of pointers. I'll stand by my original recommendation that a streaming friendly algorithm is far better suited to sorting a linked list than the usual suspects in array sorting.

Of course, a better general solution is to modify the insertion algorithm to keep the list sorted. That way a separate (inefficient) sorting step is unnecessary and the time needed to sort the list is amortized over all of the insertion operations.

[I_m_rude]

So, oh! My two professors ;) isn't merge sort is best for this ?

[Ancient Dragon]

isn't merge sort is best for this ?

Depends on how much data you are talking about. For very small quantities almost any algorithm, including bubble sort, will do. With larger quantites then bubble sort is not a good solution. There are lots of sort algorithms, Here is one of many threads that talks about sort comparisons.

[I_m_rude]

but, sir how they will work in a linked list ? how to break a linked list like we do in array ?

[Ancient Dragon]

but, sir how they will work in a linked list ? how to break a linked list like we do in array ?

What do you mean by "they"?

I posted a complete example of bubble sort

[edit]Oops! I just realized this is C forum, my example was in C++. The sort algorithm (except swapping) would be the same in both examples.

[I_m_rude]

they means merge sort and quick sort and bubble sort even. please if u really want to help, then post this in C. I dnt have idea of C++ much. so please help!