1

trying to implement bubble sort using linked list but its not working. can anyone identify the problem in my code. i think in class singlylinkedist there is a function called bubblesort in which for loop is not working, for completely sorting the linked list. It only sorts the list once but not sorts it till the size of the linked list.

#include<iostream>

using namespace std;

class Node{
    public:
        int data;
        Node *next;
        
    Node()
    {
        data = 0;
        next = NULL;
    }
    
    Node(int d)
    {
       data = d;
    }
};

class singlylinkedlist{
    public:
        Node *head,*tail;
        
        singlylinkedlist()
        {
            head = NULL;
            tail = NULL;
        }
        
        void appendNode(Node *temp)
        {
          if (head == NULL) 
          {
            head = temp;
            tail = temp;
            cout << "Node Appended" << endl;
          } 
          else 
          {
            tail->next = temp;
            tail = tail->next;
            cout << "Node Appended" << endl;
           }
        }
        
        void prependNode(Node *temp)
        {
            temp->next = head;
            head = temp;
            cout<< "Node Prepended" << endl;
        }
        
        int getdata(int pos)
        {
            Node *curr = new Node;
            curr = head;
            for(int i=1;i<pos;i++)
            {
                curr = curr->next;
            }
            return curr->data;
        }
        
        void printList() 
        {
            if (head == NULL) 
            {
              cout << "No Nodes in Singly Linked List";
            } 
            else 
            {
              cout << endl << "Singly Linked List Values : ";
              Node *temp = head;
         
              while (temp != NULL) 
              {
                cout << "--> "<<temp -> data;
                temp = temp -> next;
              }
              cout<<"\n";
            }
         }
         
         int ListSize() 
        {
            int count=0;
            if (head == NULL) 
            {
              cout << "No Nodes in Singly Linked List";
            } 
            else 
            {
              Node *temp = head;
         
              while (temp != NULL) 
              {
                temp = temp -> next;
                count = count+1;
              }
            }
            return count;
         }
         
         void bubblesort(Node *temp)
         {
            temp= head;
            Node *ptr;
            Node *prev = NULL;
            
            for(int j=0;j<ListSize();j++)
            {
                while(temp!=NULL && temp->next!=NULL){
                    
                    if(temp->data  > temp->next->data){
                        
                        if(prev == NULL){
                           ptr = temp->next;
                           temp->next = ptr->next;
                           ptr->next = temp;
                           head = prev = ptr;
                        }
                        
                        else{
                            ptr = temp->next;
                            prev->next = ptr;
                            temp->next = ptr->next;
                            ptr->next = temp;
                            prev = ptr;
                            
                        }  
                       
                     }
                     
                     else{
                        ptr = temp->next;
                        prev = temp;
                        temp = ptr;
                     }
                }
             }
                
        }
};

int main()
{
   singlylinkedlist s;
   int option;
   int data1;
   int pos;
   
   do{
    cout << "\nWhat operation do you want to perform? Select Option number. Enter 0 to exit." << endl;
    cout << "1. appendNode()" << endl;
    cout << "2. prependNode()" << endl;
    cout << "3. getdata()" << endl;
    cout << "6. printList()"  << endl;
    cout << "7. bubblesort()" << endl;
    
    cin>>option;
    
    Node *temp = new Node;
    
    switch (option) {
    case 0:
      break;
    case 1:
      cout << "Append Node Operation \nEnter data of the Node to be Appended" << endl;
      cin >> data1;
      temp->data = data1;
      temp->next = NULL;
      s.appendNode(temp);
      break;
    
    case 2:
       cout<<"Prepend Node Operation \nEnter data of the Node to be Prepended" << endl;
       cin>>data1;
       temp->data = data1;
       temp->next = NULL;
       s.prependNode(temp);
       break;
    
    case 3:
        cout<<"enter position to get data"<<endl;
        cin>>pos;
        cout<<"DATA AT GIVEN INDEX IS " << s.getdata(pos);
        break;
    
    case 6:
      s.printList();
      break;
      
    case 7:
      s.bubblesort(temp);
      s.printList();
      break;
    } 

}while (option != 0);

}
10
  • 1
    Fyi, C++ isn't Java. The allocation you do in getdata is completely pointless and leaks memory in literally two short lines. Just saying. Commented Nov 10, 2020 at 7:51
  • bro thanks for letting me know. i appreciate it.but can u just help me with my problem?? Commented Nov 10, 2020 at 7:54
  • Are you familiar with bubble sort? I.e. did you manage to program yourself a bubble sort of ints in an array? Commented Nov 10, 2020 at 7:58
  • 1
    Are you familiar with linked lists? I.e. did you manage to program yourself a linked list with insert (middle/start/end), delete(middle/start/end) and print? Commented Nov 10, 2020 at 7:59
  • @Yunnosch yes i am familiar with it. i have implemented it using array first after that i am implementing it using liked list in which i have to to sort it by swapping nodes. pls help me and resolve my problem Commented Nov 10, 2020 at 8:02

1 Answer 1

1

Setting aside the rest of the broken code, the main problem with your sort is the failure to reset prev and temp on each iteration of the most-outer loop. Each sweep of the list requires those be reset (prev should restart to null, temp should restart to head. Doing that we have:

void bubblesort()
{
    for(int j=0;j<ListSize();j++)
    {
        Node *prev = nullptr;
        Node *temp = head;
        
        while(temp != nullptr && temp->next != nullptr)
        {
            if(temp->data  > temp->next->data)
            {
                
                if(prev == nullptr)
                {
                    Node *ptr = temp->next;
                    temp->next = ptr->next;
                    ptr->next = temp;
                    head = prev = ptr;
                }
                else
                {
                    Node *ptr = temp->next;
                    prev->next = ptr;
                    temp->next = ptr->next;
                    ptr->next = temp;
                    prev = ptr;
                }
            }
            else
            {
                Node *ptr = temp->next;
                prev = temp;
                temp = ptr;
            }
        }
    }
}

Alternative

A few things to note. This is only half-bubble-sort. The very point of bubblesort is that, with each sweep the "greatest" node bubbles to the end. E.g. it need never be visited again, as nothing will be "greater" (that's how it bubbles to the end in the first place). However, with your algorithm you repeatedly sweep the entire list rather than falling short one-less node than the prior iteration.

A simple way to do this is to simply dismount the node from the list once it is at the end, and an easy way to do that is to move it to the front of a whole new chain. The algorithm then becomes.

  1. Sweep the list, bubbling the max-node of the active list to the end
  2. Detach the node from that list and prepend it to a new chain.
  3. Continue (1) and (2) this until there are no more nodes in the old list.
  4. The new chain is now the new list. Set head and you're done.

Doing this visually, suppose we had five elements in our list, and initially an empty "result" list.

list: 7 4 5 2 6
result: null

After the first pass of (1) and (2) we have:

list: 4 5 2 6
result: 7

the second pass:

list: 4 2 5
result: 6 7

the third pass:

list: 2 4
result: 5 6 7

the fourth pass:

list: 2
result: 4 5 6 7

and finally:

list: null
result 2 4 5 6 7

At this point we can simply set list to result and our list is now sorted.

An implementation that accomplishes this using pointer-to-pointer methodology is below. Note that nowhere do we fetch, nor care, about the list size (i.e. there is no call to ListSize() required).

void bubblesort()
{
    Node *result = nullptr;
    while (head != nullptr)
    {
        // starts at the beginning of the list
        Node **pp = &head;
        while ((*pp)->next != nullptr)
        {
            Node **pp2 = &(*pp)->next;
            if ((*pp2)->data < (*pp)->data)
            {
                // swap pointers, then swap back their next members.
                std::swap(*pp, *pp2);
                std::swap((*pp)->next, (*pp2)->next);
            }
            
            // advance to next node in the list.
            pp = &(*pp)->next;
        }
        
        // prepend to new list, unlink from old one.
        (*pp)->next = result;
        result = *pp;
        *pp = nullptr;
    }
    
    // new list is built
    head = result;
}

Testing

Generate a random sequence of twenty values in {1..99}, print, then sort, then print again. For spice, all odd values generated are initially prepended; all even values are appended. Once the list is built we turn our bubblesort loose on it, and then print the final result.

#include <iostream>
#include <utility>
#include <random>

class Node{
public:
    int data;
    Node *next;
    
    Node(int d=0)
        : data(d)
        , next(nullptr)
    {
    }
};

class singlylinkedlist{
public:
    Node *head,*tail;
    
    singlylinkedlist()
        : head(nullptr)
        , tail(nullptr)
    {
    }
    
    ~singlylinkedlist()
    {
        while (head)
        {
            Node *tmp = head;
            head = head->next;
            delete tmp;
        }
    }
    
    // squelch these; copying not supported.
    singlylinkedlist(const singlylinkedlist&) = delete;
    singlylinkedlist& operator =(const singlylinkedlist&) = delete;
    
    void appendNode(int data)
    {
        Node *p = new Node(data);
        if (head == nullptr)
            head = p;
        else
            tail->next = p;
        tail = p;
    }
    
    void prependNode(int data)
    {
        Node *p = new Node(data);
        p->next = head;
        if (head == nullptr)
            tail = p;
        head = p;
    }
    
    int getdata(int pos)
    {
        Node *curr = head;
        while (curr != nullptr && pos-- > 0)
            curr = curr->next;
        return curr ? curr->data : 0; // TODO: throw an exception if out of range?
    }
    
    void printList() const
    {
        for (const Node *p = head; p != nullptr; p = p->next)
            std::cout << p->data << ' ';
        std::cout << '\n';
    }
    
    int size() const
    {
        int count=0;
        for (const Node *p = head; p != nullptr; p = p->next)
            ++count;
        return count;
    }

    void bubblesort()
    {
        Node *result = NULL;
        while (head != nullptr)
        {
            // starts at the beginning of the list
            Node **pp = &head;
            while ((*pp)->next != nullptr)
            {
                Node **pp2 = &(*pp)->next;
                if ((*pp2)->data < (*pp)->data)
                {
                    // swap pointers, then swap back their next members.
                    std::swap(*pp, *pp2);
                    std::swap((*pp)->next, (*pp2)->next);
                }
                
                // advance to next node in the list.
                pp = &(*pp)->next;
            }
            
            // link to new list, unlink from old one.
            (*pp)->next = result;
            result = *pp;
            *pp = nullptr;
        }
        
        // new list is built
        head = result;
    }
    
};

int main()
{
    // fixed seed for repetitive testing. replace 42 with
    //  std::random_device{}() for random sequence
    std::mt19937 rng{ 42 };
    std::uniform_int_distribution<> dist(1,99);
    
    singlylinkedlist s;
    for (int i=0; i<20; ++i)
    {
        int data = dist(rng);
        if (data % 2)
            s.prependNode(data);
        else
            s.appendNode(data);
    }
    s.printList();
    
    s.bubblesort();
    s.printList();
}

Output

53 3 75 75 87 83 21 61 15 93 52 72 88 24 22 2 88 30 38 2 
2 2 3 15 21 22 24 30 38 52 53 61 72 75 75 83 87 88 88 93 
Sign up to request clarification or add additional context in comments.

2 Comments

man you really solved my problem. Love u bro. I cant thank u enough.
Great. Learn how to accept an answer and I'll be doubly-impressed.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.