-2

I'm currently learning about many different ways of sorting data. I'm trying to implement insertion sort on doubly linked list using C++. I understand the concept of using it on an array. But, i'm having difficult time figuring out why my "while" loop is looping indefinitely.

Here is my code : 

template <class T>
class Node
{
protected:
  T item;
  Node<T>* prev;
  Node<T>* next;

public :
  Node()
  {
    prev=nullptr;
    next=nullptr;
  }
};

//InsertionSort
void insertionSort()
{
    Node<T>* current = head->next;
    int count = 1;

    for(current; current != nullptr; current=current->next)
    {

        Node<T>* j = current;
        Node<T>* bj = j->prev;

        while(j != nullptr && j->item < bj->item)
        {
            cout << count++ <<  "Hi" << endl;
            Node<T>* temp = j->next;

            j->next = bj;
            bj->prev = j;

            bj->next = temp;
            temp->prev = bj;
        }
    }
}

I added int count to see how many times my loops occur. My for loop is supposed to occur 920 times, and it does. But, my while loop seems to be looping for indefinite amount of times.

Please help.

jvsper
  • 41
  • 4
  • Stack Overflow isn't a free debugging service, and you should show your attempts at debugging the code with a debugger or other simpler methods such as debug print statements. You can also test each part of the code separately to figure out exactly which part of the code is causing the problem, and make a [mcve]. This won't be the only time you end up with a bug in your code, and learning to debug your programs will help you much more than having someone find the bug for you. http://idownvotedbecau.se/nodebugging/ – eesiraed Jul 18 '18 at 04:23
  • I added cout< – jvsper Jul 18 '18 at 04:27
  • There's a lot more to try than just counting loop iterations. For example, figure out what the pointers are pointing to. The best way would be to step through your code with a debugger. I can already see the bug just by reading your code, and I think you will be able to figure this out yourself (at least part of it). – eesiraed Jul 18 '18 at 04:40
  • @jvsper *My while loop seems to be looping for indefinite amount of times* -- Because this condition `j != nullptr && j->item < bj->item` is always true. Why else would the `while` loop never end? – PaulMcKenzie Jul 18 '18 at 04:40
  • Possible duplicate of [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – Raedwald Jul 18 '18 at 05:33

1 Answers1

1

It runs forever because your pointers get all screwed up. Lets say you started with bj, j, and some node a and b:

NULL <--- NodeA <---> Bj <---> J <---> NodeB ---> NULL

At the end of a single while loop iteration your nodes are in this state:

NodeA:          NULL <--- NodeA ---> Bj
Bj:             j    <---   Bj  ---> NodeB
J:              Bj   <---   J   ---> Bj
NodeB:          Bj   <--- NodeB ---> NULL

As you can see j now points to bj in both directions, and no 'prev' points at NodeA.

After a second iteration (and all subsequent onto infinity iterations) your nodes would be as follows:

NodeA:          NULL <--- NodeA ---> Bj
Bj:             Bj   <---   Bj  ---> Bj
J:              Bj   <---   J   ---> Bj
NodeB:          Bj   <--- NodeB ---> NULL

As you can see now both j and bj point to bj in both directions.

"Please help" is rather vague so I've just helped you identify the actual behavior. In the future I encourage you to pen and paper (or something similar) write down an expected result from a test case, and then the actual result as you step through the code.

Jonah Simon
  • 29
  • 4