sorting help

hoe can v implement the merge sort algorithm in linked list ??
tthnx

Comments

  • : hoe can v implement the merge sort algorithm in linked list ??
    : tthnx
    :


    its not possible to sort a linked list directly. So the answer to your question is No. you can, however, create an array of pointers to each of the nodes in the linked list, then sort that array of pointers.
  • : : hoe can v implement the merge sort algorithm in linked list ??
    : : tthnx
    : :
    :
    :
    : its not possible to sort a linked list directly. So the answer to your question is No. you can, however, create an array of pointers to each of the nodes in the linked list, then sort that array of pointers.
    :

    can u explain me with code ,so that i can understand better??
  • [b][red]This message was edited by stober at 2006-3-7 11:23:2[/red][/b][hr]
    :
    : can u explain me with code ,so that i can understand better??
    :


    ok, here is a pretty simple example, but uses bubble sort.
    [code]
    #include
    #include
    #include

    struct node
    {
    char name[40];
    struct node* next;
    };

    struct node* head = 0;

    struct node* FindTail()
    {
    if(head == 0)return 0;
    struct node* n = head;
    while(n->next)
    n = n->next;
    return n;
    }


    struct node* AddNode(const char* name)
    {
    struct node* newnode;
    struct node* tail = FindTail();
    newnode = (struct node*)malloc(sizeof(struct node));
    newnode->next = 0;
    strcpy(newnode->name, name);

    if(tail == 0)
    {
    head = newnode;
    }
    else
    {
    tail->next = newnode;
    }
    return newnode;
    }


    int main(int argc, char* argv[])
    {
    int i,j, nNodes;
    AddNode("Smith");
    AddNode("Jones");
    AddNode("Adam");

    // create an array
    struct node* array[5];
    struct node* n = head;
    nNodes = 0;
    while(n != 0)
    {
    array[nNodes] = n;
    n = n->next;
    nNodes++;
    }
    // now sort the array, but you have to exchange the node's data
    // not the pointers. Will use bubble sort here because
    // it is simple to code

    for(i = 0; i < nNodes -1 ; i++)
    {
    for(j = i+1; j < nNodes; j++)
    {
    if( strcmp(array[i]->name, array[j]->name) > 0)
    {
    // swap the data
    char temp[40];
    strcpy(temp,array[i]->name);
    strcpy(array[i]->name,array[j]->name);
    strcpy(array[j]->name,temp);
    }
    }
    }
    n = head;
    while(n)
    {
    printf("%s
    ",n->name);
    n = n->next;
    }
    return 0;
    }
    [/code]




  • : [b][red]This message was edited by stober at 2006-3-7 11:23:2[/red][/b][hr]
    : :
    : : can u explain me with code ,so that i can understand better??
    : :
    :
    :
    : ok, here is a pretty simple example, but uses bubble sort.
    : [code]
    : #include
    : #include
    : #include
    :
    : struct node
    : {
    : char name[40];
    : struct node* next;
    : };
    :
    : struct node* head = 0;
    :
    : struct node* FindTail()
    : {
    : if(head == 0)return 0;
    : struct node* n = head;
    : while(n->next)
    : n = n->next;
    : return n;
    : }
    :
    :
    : struct node* AddNode(const char* name)
    : {
    : struct node* newnode;
    : struct node* tail = FindTail();
    : newnode = (struct node*)malloc(sizeof(struct node));
    : newnode->next = 0;
    : strcpy(newnode->name, name);
    :
    : if(tail == 0)
    : {
    : head = newnode;
    : }
    : else
    : {
    : tail->next = newnode;
    : }
    : return newnode;
    : }
    :
    :
    : int main(int argc, char* argv[])
    : {
    : int i,j, nNodes;
    : AddNode("Smith");
    : AddNode("Jones");
    : AddNode("Adam");
    :
    : // create an array
    : struct node* array[5];
    : struct node* n = head;
    : nNodes = 0;
    : while(n != 0)
    : {
    : array[nNodes] = n;
    : n = n->next;
    : nNodes++;
    : }
    : // now sort the array, but you have to exchange the node's data
    : // not the pointers. Will use bubble sort here because
    : // it is simple to code
    :
    : for(i = 0; i < nNodes -1 ; i++)
    : {
    : for(j = i+1; j < nNodes; j++)
    : {
    : if( strcmp(array[i]->name, array[j]->name) > 0)
    : {
    : // swap the data
    : char temp[40];
    : strcpy(temp,array[i]->name);
    : strcpy(array[i]->name,array[j]->name);
    : strcpy(array[j]->name,temp);
    : }
    : }
    : }
    : n = head;
    : while(n)
    : {
    : printf("%s
    ",n->name);
    : n = n->next;
    : }
    : return 0;
    : }
    : [/code]
    :
    :
    Thnx a million my brother
    :
    :
    :

  • : [b][red]This message was edited by stober at 2006-3-7 11:23:2[/red][/b][hr]
    : :
    : : can u explain me with code ,so that i can understand better??
    : :
    :[red] Hei brother , do help me below[/red]
    :
    : ok, here is a pretty simple example, but uses bubble sort.
    : [code]
    : #include
    : #include
    : #include
    :
    : struct node
    : {
    : char name[40];
    : struct node* next;
    : };
    :
    : struct node* head = 0;
    :
    : struct node* FindTail()
    : {
    : if(head == 0)return 0;
    : struct node* n = head;
    : while[red](n->next==NULL)// Am i correct here??[/red]
    : n = n->next;
    : return n;
    : }
    :
    :
    : struct node* AddNode(const char* name)
    : {
    : struct node* newnode;
    : struct node* tail = FindTail();
    : newnode = (struct node*)malloc(sizeof(struct node));
    : newnode->next = 0;
    : strcpy(newnode->name, name);
    :
    : if(tail == 0)
    : {
    : head = newnode;
    : }
    : else
    : {
    : tail->next = newnode;
    : }
    : return newnode;
    : }
    :
    :
    : int main(int argc, char* argv[])
    : {
    : int i,j, nNodes;
    : AddNode("Smith");
    : AddNode("Jones");
    : AddNode("Adam");
    :
    : // create an array
    : struct node* array[5];
    : struct node* n = head;
    : nNodes = 0;
    : while(n != 0)
    : {
    : array[nNodes] = n;
    : n = n->next;
    : nNodes++;
    : }
    : // now sort the array, but you have to exchange the node's data
    : // not the pointers. Will use bubble sort here because
    : // it is simple to code
    :
    : for(i = 0; i < nNodes -1 ; i++)
    : {
    : for(j = i+1; j < nNodes; j++)
    : {
    : if( strcmp(array[i]->name, array[j]->name) > 0)
    : {
    : // swap the data
    : char temp[40];
    : strcpy(temp,array[i]->name);
    : strcpy(array[i]->name,array[j]->name);
    : strcpy(array[j]->name,temp);
    : }
    : }
    : }
    : n = head;
    : while(n)
    : {
    : printf("%s
    ",n->name);
    : n = n->next;
    : }
    : return 0;
    : }
    : [/code]
    :
    :
    :
    :
    :

Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories