Merge Sort on linked list..my code is almost done..please help me onit

Discussion in 'C++' started by alcondor, Apr 26, 2010.

  1. alcondor

    alcondor Guest

    I have worked on this code hours, and get it to work finally on Linux
    Debian..
    its basically sort a linked list --bubble sort. Also I added a piece
    of code to the main function to measure the execution time of the
    bubble sort function

    what I am trying now is to get a merge sort from another source code
    and have it to work on mine and measure the time of execution too

    here is my code --

    #include <iostream>
    #include <time.h>

    using namespace std;
    class node
    {
    friend class linklist;
    int value;
    node *next;

    };

    class linklist
    {
    private:
    node *first;
    node *last;
    public:
    linklist(){ first = NULL; }
    ~linklist(){};
    void addnode();
    void BubbleSort();
    //void MergeSort();
    void displaynode();

    };

    void linklist :: addnode()
    {
    node *newno;
    do
    {
    newno = new node;
    newno->next=NULL;
    //cout<<"Number : ";
    cin>>newno->value;
    if(first==NULL)
    first=last=newno;
    else
    {
    last->next=newno;
    last=newno;
    }
    }while(newno->value != 0);

    }

    void linklist :: displaynode()
    {
    //cout<<"---------------------\nSorted values :\n";
    node *curno=first;
    while(curno)
    {
    cout<<curno->value<<'\n';
    curno=curno->next;
    }

    }

    void linklist ::BubbleSort()
    {
    int x,y,m,n=0,put;
    node *q, *p, *t;
    for(node*q = first ; q ; q=q->next) //balad shodid;
    ++n;

    for(x=1 , t = first ; x<=n-1 ; t = t->next , ++x)
    for( y=0 , p = first ; y<n-x ; p = p->next , ++y)
    if(p->value > (p->next)->value)
    {
    put = p->value;
    p->value = (p->next)->value;
    (p->next)->value = put;
    }

    }

    /*
    void linklist ::MergeSort()
    {

    // your help here please
    // your help here please
    // your help here please
    // your help here please
    }

    */

    int main()
    {
    linklist sl;
    sl.addnode();
    // measure excution time
    // stolen from http://bytes.com/topic/c/answers/576635-there-timer-function-c
    time_t start_time= clock(); //set the clock
    sl.BubbleSort();
    float time1 = (float) (clock() - start_time) /
    CLOCKS_PER_SEC; //
    calculate excution time
    sl.displaynode();
    printf("Bubble-sorting took %f seconds to finish\n", time1);

    return 0;

    }

    ---- end of code

    and here is the merge sort code from another program..I just want to
    get the merge function in this code to work on mine..my code is the
    first one ..the one above

    --merge sort -- code--------
    #include <iostream>
    using namespace std;

    #define NULL 0

    class LinkList
    {
    private:
    struct Node
    {
    Node* prev;
    int value;
    Node *next;
    };
    Node *first;

    public :

    LinkList()
    {
    Node *t1 = new Node();
    t1->prev = NULL;
    t1->value = 4;
    t1->next = NULL;
    first = t1;

    Node *t2 = new Node();
    t2->prev = t1;
    t2->value = 6;
    t2->next = NULL;
    t1->next = t2;

    Node *t3 = new Node();
    t3->prev = t2;
    t3->value = 1;
    t3->next = NULL;
    t2->next = t3;

    Node *t4 = new Node();
    t4->prev = t3;
    t4->value = 5;
    t4->next = NULL;
    t3->next = t4;

    Node *t5 = new Node();
    t5->prev = t4;
    t5->value = 8;
    t5->next = NULL;
    t4->next = t5;

    Node *t6 = new Node();
    t6->prev = t5;
    t6->value = 1;
    t6->next = NULL;
    t5->next = t6;

    Node *t7 = new Node();
    t7->prev = t6;
    t7->value = 0;
    t7->next = NULL;
    t6->next = t7;
    }

    ~LinkList()
    {
    Node *temp = first, *current = first;
    while(current != NULL)
    {
    temp = current->next;
    delete current;
    current = temp;
    }

    }

    void Display()
    {
    Node *temp;
    for(temp = first; temp != NULL; temp = temp->next)
    {
    cout<<temp->value<<" , ";
    }
    cout<<endl;
    }

    void Sort()
    {
    Node *current, *cur;

    for(current = first; current->next != NULL; current = current-
    >next)


    {
    Node *minimum = current;
    for(cur = current ; cur != NULL; cur = cur->next)
    {
    if(minimum->value > cur->value)
    {
    minimum = cur;
    }
    }
    if(minimum != current)
    {
    Node *current_previous, *current_next, *min_previous,
    *min_next;

    // Initialize them
    current_next = current->next;
    min_previous = minimum->prev;
    min_next = minimum->next;
    current_previous = current->prev;

    if(current_previous == NULL)
    {
    // Change the First Node
    first = minimum;
    }
    if(current->next == minimum)
    {
    // Nodes are Adjacent
    minimum->prev = current_previous;
    minimum->next = current;

    current->prev = minimum;
    current->next = min_next;

    if(min_next)
    {
    min_next->prev = current;
    }
    if(current_previous)
    {
    current_previous->next = minimum;
    }
    }
    else
    {
    minimum->prev = current_previous;
    minimum->next = current_next;

    current->prev = min_previous;
    current->next = min_next;

    if(current_next)
    {
    current_next->prev = minimum;
    }
    if(min_previous)
    {
    min_previous->next = current;
    }
    if(min_next)
    {
    min_next->prev = current;
    }
    if(current_previous)
    {
    current_previous->next = minimum;
    }
    }
    current = minimum;
    }
    }

    }

    };

    int main()
    {
    LinkList list;

    cout<<"LinkList = ";

    list.Display();

    cout<<"\n\nSorting \n\n";

    list.Sort();

    cout<<"LinkList = ";

    list.Display();
    return 0;

    }

    ----- code ends----

    I know it sounds easy, and should be easy.. but I am getting all kind
    of warnings and errors..if you have better code please help me with
    it..

    my goal is just to have the merge sort function on the second code to
    work on the first one along with bubble sort..I will add an option to
    the user to choose which one he wants to perform..the idea is to
    measue the speed of the merge sort and the bubble sort..we all know
    merge sort is faster..but I just want to demo it

    I run my code like this
    g++ bubblesort.cpp -o bs.o
    then I feed it a list of numbers like this
    more list.txt | ./bs.out

    thank you very much for your time
     
    alcondor, Apr 26, 2010
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Booser
    Replies:
    1
    Views:
    1,319
    CBFalconer
    Feb 9, 2004
  2. dont bother
    Replies:
    2
    Views:
    382
    Josiah Carlson
    Mar 5, 2004
  3. fool
    Replies:
    14
    Views:
    525
    Barry Schwarz
    Jul 3, 2006
  4. c
    Replies:
    9
    Views:
    793
    Seebs
    Apr 26, 2010
  5. Navin
    Replies:
    1
    Views:
    728
    Ken Schaefer
    Sep 9, 2003
Loading...

Share This Page