I am trying to sort a doubly linked list with the nodes for an assignment because thats what the spec wants me to do. I thought to basically make a new list with the sorted and then assign the head and tail
The two .h files of my program:
#ifndef SN_H
#define SN_H
#include <string>
#include <sstream>
//SortNode class implementation here
template <class T>
class SortNode
{
protected:
T value;
public:
SortNode<T> * next;
SortNode<T> * prev;
SortNode(T);
std :: string print();
T getValue();
};
#include "SortNode.cpp"
#endif
#ifndef DLL_H
#define DLL_H
#include "SortNode.h"
template <class T>
class SortList
{
private:
bool ascending;
SortNode<T> * head;
SortNode<T> * tail;
public:
SortList(bool);
void add(SortNode<T>* a) ;
SortNode<T>* remove(T val);
void setAsc(bool a);
void sort() ;
string print() ;
SortNode<T>*getHead() ;
string debug() ;
};
#include "SortList.cpp"
#endif
I have tried to sort it like i described but then it gets stuck in a loop and don't have an idea how to do this.
This is the sort function that gives me problems.
template <class T>
void SortList<T> :: sort()
{
cout<<"above if "<<endl;
if (ascending == true)
{
SortNode<T> * node = head, *ptr = NULL ,*sortedh = NULL, *sortedt = NULL, *newnode = NULL;
while (node != NULL)
{
newnode = node;
if (!sortedh)
{
sortedh = node;
sortedt = node;
}
else
{
ptr = head;
while (ptr!= NULL && ptr -> getValue() < newnode -> getValue())
{
ptr = ptr -> next;
}
if (!ptr)
{
sortedt -> next = newnode;
newnode ->prev = sortedt;
sortedt = newnode;
}
else
{
if (ptr ->prev == NULL)
{
newnode -> next = ptr;
ptr -> prev =newnode;
sortedh = newnode;
}
else
{
ptr -> prev -> next = newnode;
newnode -> prev =ptr -> prev;
newnode -> next =ptr;
ptr -> prev = newnode;
}
}
}
node = node -> next;
}
}
}
Any help will be appreciated.
The code has bugs.
For example in this code snippet there are even two bugs.
if (!sortedh)
{
sortedh = node;
sortedt = node;
}
else
{
ptr = head;
//...
Instead you need to write
if (!sortedh)
{
sortedh = node;
sortedt = node;
node->next = nullptr;
}
else
{
ptr = sortedh;
//...
Or in this if statement
if (!ptr)
{
sortedt -> next = newnode;
newnode ->prev = sortedt;
sortedt = newnode;
}
you forgot to set the data member next of the node pointed to by the pointer newnode like
if (!ptr)
{
sortedt -> next = newnode;
newnode ->prev = sortedt;
newnode->next = nullptr;
sortedt = newnode;
}
Or in this if statement
if (ptr ->prev == NULL)
{
newnode -> next = ptr;
ptr -> prev =newnode;
sortedh = newnode;
}
you forgot to set the data member prev of the node pointed to by the pointer newnode as for example
newnode -> next = ptr;
newnode->prev = ptr->prev; or newnode->prev = nullptr;
And there is one more problem. The data member next of the node pointed to by the pointer node can be changed. So this statement
node = node -> next;
can result in that the pointer node can point to an already processed node.
Also the function does not set the pointers head and tail.
Here is a demonstration program that shows how the function that implements the insertion sort method can be defined. To simplify writing the program I have made some minor changes in the class definitions.
#include <iostream>
#include <cstdlib>
#include <ctime>
//SortNode class implementation here
template <class T>
class SortNode
{
protected:
T value;
public:
SortNode *prev;
SortNode *next;
SortNode( const T &value, SortNode *prev = nullptr, SortNode *next = nullptr )
{
this->value = value;
this->prev = prev;
this->next = next;
}
const T & getValue() const
{
return value;
}
T & getValue()
{
return value;
}
};
template <class T>
class SortList
{
private:
bool ascending = true;
SortNode<T> *head = nullptr;
SortNode<T> *tail = nullptr;
public:
SortList() = default;
void add( const T &value )
{
SortNode<T> *new_node = new SortNode<T>{ value, tail, nullptr };
if (!head)
{
head = new_node;
}
else
{
tail->next = new_node;
}
tail = new_node;
}
SortNode<T> *remove( T val );
void setAsc( bool a );
void sort();
std::ostream &print( std::ostream &os = std::cout ) const
{
for (SortNode<T> *current = head; current != nullptr; current = current->next)
{
os << current->getValue() << " -> ";
}
return os << "null";
}
SortNode<T> *getHead();
};
template <class T>
void SortList<T> ::sort()
{
if (ascending)
{
SortNode<T> *node = head, *sortedh = nullptr, *sortedt = nullptr;
while (node != NULL)
{
SortNode<T> *newnode = node;
SortNode<T> *next = node->next;
if (!sortedh)
{
sortedh = node;
sortedt = node;
node->next = nullptr;
}
else
{
SortNode<T> *ptr = sortedh;
while (ptr != NULL && !( newnode->getValue() < ptr->getValue() ) )
{
ptr = ptr->next;
}
if (!ptr)
{
sortedt->next = newnode;
newnode->prev = sortedt;
newnode->next = nullptr;
sortedt = newnode;
}
else
{
if (ptr->prev == NULL)
{
newnode->next = ptr;
newnode->prev = nullptr;
ptr->prev = newnode;
sortedh = newnode;
}
else
{
ptr->prev->next = newnode;
newnode->prev = ptr->prev;
newnode->next = ptr;
ptr->prev = newnode;
}
}
}
node = next;
}
head = sortedh;
tail = sortedt;
}
}
int main()
{
SortList<int> list;
const int N = 20;
srand( ( unsigned int )time( nullptr ) );
for (int i = 0; i < N; i++)
{
list.add( rand() % N );
}
list.print() << '\n';
list.sort();
list.print() << '\n';
}
The program output might look like
17 -> 12 -> 0 -> 12 -> 8 -> 8 -> 8 -> 13 -> 4 -> 7 -> 8 -> 11 -> 7 -> 8 -> 18 -> 4 -> 16 -> 18 -> 18 -> 3 -> null
0 -> 3 -> 4 -> 4 -> 7 -> 7 -> 8 -> 8 -> 8 -> 8 -> 8 -> 11 -> 12 -> 12 -> 13 -> 16 -> 17 -> 18 -> 18 -> 18 -> null