Everybody! This is important. In a few days, these forums will be moving over to using the totally sweet Discourse platform. To ensure this migration happens smoothly with no loss of content, these forums are currently in a read-only mode. I do apologize for the inconvenience.

There is never a good time to turn the forums off for an extended period of time, but I promise the new forums will be a billion times better. I'm pretty sure of it.

See you all on the other side in a few days, and if you have any (non-technical) questions, please e-mail me at kirupa@kirupa.com. For technical questions, try to find a tutorial that corresponds to what you are looking for and post in the comments section of that page.

Cheers,
Kirupa

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