Results 1 to 8 of 8

Thread: merge sort on linked list

  1. #1

    Fla Script merge sort on linked list

    does anyone know or have any tips on using the mergesort algorithm on a linked list ?
    I've looked up on goodle and didnt get much info about it, other than one algorithm i have a hard time understanding

    thx

  2. #2
    i dont see how it's possible. merge sort requires a list be indexed. a linked list per se is not indexed.

  3. #3
    it is possible on doubly linked lists. Thats the only way i got it to work, but after reading and asking around a little, i hear the fastest way to sort a linked list is to sort on insertion in the list. the algorithm is also much simpler

  4. #4
    here is a piece of code pretty usefull for sorting linked lists.

  5. #5
    1,839
    posts
    Registered User
    usually a linked list is
    Head ->Node->Node->Node->Node->Node->End

    For Example (C++ code)
    Node.h
    Code:
    class node{
      public:
         node(void);  // constructor
         void setData(int);
         int getData(void);
         void insert(node &);
         void printList(void);
      private:
         int data;
         node *next;
    };
    
    node::node(void){
       next = NULL;
    }
    
    void node::setData(int d){
       data = d;
    }
    
    int node::getData(void){
       return data;
    }
    
    void node::insert(node &p){
       p.next = next;
       next = &p;
    }
    
    void node::printList(void){
       if(next != NULL){
          cout << next->data << endl;
          next->printList();
       }
    }
    Main.cpp
    Code:
    #include<iostream>
    using namespace std;
    #include"node.h"
    
    int main(){
       node head;
       node *p;
       int temp;
       do{
          cout << "Next value (enter 0 when finished): ";
          cin >> temp;
          if(temp != 0){
             p = new node;
             p -> setData(temp);
             head.insert(*p);
          }
       }while(temp != 0);  
       head.printList();
    }
    You cannot do a merge sort since like the man said it requires indexes ....

    but i guess you could add a (bubble) sort function to your node class and list class or file
    Code:
    //add private var int isSet to the class definition as well as the definition for sort
    //in your node constructor the set isSet to 0.  in the setData function set isSet = 1
    
    int node::sort(int isChanged){
         if(next != NULL){//if next node has data     
               if(isSet){ // if this node has data
                   if(data > next->data){//swap nodes
                            int tempData = data;
                            data = next->data;
                            next->data = tempData;
                            isChanged = 1;
                   }
                }
              return next->sort(isChanged);
         }else{//if we have reached the end of the list
              return isChanged;//return 0 if it has been unchanged 1 if its been changed
         } 
    }
    and then in your main.cpp
    Code:
    int isChanged;
    do{
        isChanged = head.sort(0);//start with is changed = 0 on each loop
    }while(isChanged);
    and that will sort your linked list from smallest to largest using a bubble sort

  6. #6
    You cannot do a merge sort since like the man said it requires indexes ....
    You can do a merge sort (saying nothing of efficiency), since you can get the index of a given node by starting at the head and counting the number of nodes that you traverse through.

  7. #7
    yeah you can merge sorts on doubly linked lists, it's just not efficient, and i think the list needs to to be circular.
    We had that as an exercise in a exam in school, but the best is to sort as you insert.

    but i guess you could add a (bubble) sort function to your node class and list class or file
    I'm using C, there are no classes in C (and that's a real bummer).

  8. #8
    Quote Originally Posted by eirche View Post
    i dont see how it's possible. merge sort requires a list be indexed. a linked list per se is not indexed.
    Not possible?

    HA! You're joking right?

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

Home About kirupa.com Meet the Moderators Advertise

 Link to Us

 Credits

Copyright 1999 - 2012