I need help with a homework assignment. I am to create a doubly linked list that reads the numbers from file and then compare the time it takes to sort the numbers using three different sorting algorithms. Here is the code that I have. The algorithms are not working(insertion sort is not sorting and the others are giving many errors) can anyone help?
#ifndef DOUBLYLINKED_H
#define DOUBLYLINKED_H
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "Node.h"
template<typename TYPE>
class DoublyLinked
{
public:
DoublyLinked()
:headPtr(nullptr), tailPtr(nullptr)
{
}
//destructor
~DoublyLinked()
{
if (!isEmpty())
{
std::cout << "Destroying Nodes..." << std::endl;
Node<TYPE> *currPtr = headPtr;
Node<TYPE> *tempPtr = nullptr;
while (currPtr != nullptr)
{
tempPtr = currPtr;
std::cout << "Deleting: " << tempPtr->data << std::endl;
currPtr = currPtr->nextPtr;
delete tempPtr;
}
}
std::cout << "All nodes destroyed." << std::endl;
}
void mergeSort()
{
clock_t time = 0;
time = clock();
mergeSortHelper(headPtr);
time = clock() - time;
print();
std::cout << "The time it took to complete this function is " << ((float)time / CLOCKS_PER_SEC) << " seconds.\n";
}
void insertionSort()
{
clock_t time = 0;
time = clock();
insertionSortHelper(headPtr);
time = clock() - time;
print();
std::cout << "The time it took to complete this function is " << ((float)time / CLOCKS_PER_SEC) << " seconds.\n";
}
bool isEmpty() const
{
if (headPtr == nullptr && tailPtr == nullptr)
{
return true;
}
else
return false;
}
void addNode(const TYPE &value)
{
Node<TYPE> *newPtr = getNewNode(value);
if (isEmpty())
headPtr = tailPtr = newPtr;//add first node to list
else
{
tailPtr->nextPtr = newPtr;
tailPtr = newPtr;
}
}
bool Delete(TYPE key)
{
if (!isEmpty())
{
Node<TYPE> *currPtr = headPtr, *tempPtr;
while (currPtr != nullptr)
{
if (currPtr->data == key)
{
if (currPtr->prevPtr == nullptr)
{
headPtr = currPtr->nextPtr;
delete currPtr;
std::cout << key << " has been deleted.\n";
break;
}
else if (currPtr->nextPtr == nullptr)
{
tailPtr = currPtr->prevPtr;
delete currPtr;
std::cout << key << " has been deleted.\n";
break;
}
else
{
tempPtr = currPtr->prevPtr;
tempPtr->nextPtr = currPtr->nextPtr;
delete currPtr;
std::cout << key << " has been deleted.\n";
break;
}
}
else
{
tempPtr = currPtr;
currPtr = currPtr->nextPtr;
}
}
if (currPtr == nullptr)
{
std::cout << key << " is not in the list.\n";
return false;
}
}
else
{
std::cout << "\nThe list is empty. There is nothing to delete.\n";
return false;
}
return true;
}
Node<TYPE>* mergeSortHelper(Node<TYPE> *subListA)
{
Node<TYPE> *subListB;
if ((subListA == nullptr) || (subListA->nextPtr == nullptr))
return nullptr;
subListB = split(subListA);
return merge(mergeSortHelper(subListA), mergeSortHelper(subListB));
}
Node<TYPE>* merge(Node<TYPE> *subListA, Node<TYPE> *subListB)
{
if (subListA == nullptr)
return subListB;
else if (subListB == nullptr)
return subListA;
else if (subListA->data <= subListB->data)
{
subListA->nextPtr = merge(subListA->nextPtr, subListB);
return subListA;
}
else
{
subListB->nextPtr = merge(subListA, subListB->nextPtr);
return subListB;
}
}
Node<TYPE>* split(Node<TYPE> *source)
{
Node<TYPE> *secondNode;
if (source == nullptr || source->nextPtr == nullptr)//in the case there is only one item in the list or the list is empty
{
return nullptr;
}
else
{
secondNode = source->nextPtr;
source->nextPtr = secondNode->nextPtr;
secondNode->nextPtr = split(secondNode->nextPtr);
return secondNode;
}
}
void quickSort()
{
clock_t time = 0;
time = clock();
quickSortHelper(headPtr, tailPtr);
time = clock() - time;
std::cout << "The time it took to complete this function is " << ((float)time / CLOCKS_PER_SEC) << " seconds.\n";
}
void quickSortHelper(Node<TYPE> *l, Node<TYPE> *h)
{
if (h != nullptr && l != h && l != h->nextPtr)
{
Node<TYPE> *p = partition(l, h);
quickSortHelper(l, p->prevPtr);
quickSortHelper(p->nextPtr, h);
}
}
Node<TYPE>* partition(Node<TYPE> *l, Node<TYPE> *h)
{
//set h as pivot
int x = h->data;
Node<TYPE> *i = l->prevPtr;
for (Node<TYPE> *j = l; j != h; j = j->nextPtr)
{
if (j->data <= x)
{
i = (i == NULL) ? l : i->nextPtr;
swap((i->data), (j->data));
}
}
i = (i == NULL) ? l : i->nextPtr;
swap((i->data), (h->data));
return i;
}
void swap(TYPE a, TYPE b)
{
TYPE t = a;
a = b;
b = t;
}
void insertionSortHelper(Node<TYPE> *q)
{
int n;
Node<TYPE> *curr;
curr = q;
if (curr->nextPtr == NULL)
return;
while (curr != NULL)
{
n = 0;
Node<TYPE> *ptr = curr;
Node<TYPE> *temp = curr->nextPtr;
curr = curr->nextPtr;
while (temp != NULL && (ptr->data) > (temp->data))
{
n++;
temp = temp->prevPtr;
}
if (n)
{
(ptr->prevPtr)->nextPtr = ptr->nextPtr;
if (ptr->nextPtr != nullptr)
{
(ptr->nextPtr)->prevPtr = ptr->prevPtr;
}
if (temp == nullptr)
{
temp = *q;
ptr->prevPtr = nullptr;
ptr->nextPtr = temp;
ptr->nextPtr->prevPtr = ptr;
*q = ptr;
}
else
{
temp = temp->nextPtr;
(temp->prevPtr)->nextPtr = ptr;
ptr->prevPtr = temp->prevPtr;
temp->prevPtr = ptr;
ptr->nextPtr = temp;
}
}
}
}
void print() const
{
if (isEmpty())
{
std::cout << "The list is empty." << std::endl;
return;
}
Node<TYPE> *currPtr = headPtr;
std::cout << "The list contains: ";
while (currPtr != nullptr)
{
std::cout << currPtr->data << ' ';
currPtr = currPtr->nextPtr;
}
std::cout << "\n\n";
}
private:
Node<TYPE> *headPtr; //pointer to first node in the list
Node<TYPE> *tailPtr; //pointer to the last node in the list
Node<TYPE> *getNewNode(const TYPE &value)
{
return new Node<TYPE>(value);
}
};
#endif
