Homework SourseYou must also write a function that converts the linked list
You must also write a function that converts the linked list to an array, to be used by the quicksort.
The insertionSort must sort the linked list.
The quickSort should be written using the array you converted from the linked list.
The heapsort kind of makes an array anyhow, so use that.
#include \"Node.hpp\"
#include \"LLSE.hpp\"
#include <iostream>
#include <stdlib.h>
#include <string>
using namespace std;
LLSE::LLSE() {
first = NULL;
last = NULL;
size = 0;
}
LLSE::~LLSE() {
Node *tmp = first;
for(int i = 0; i < size; i++) {
tmp = first->next;
delete first;
first = tmp;
}
}
void LLSE::printLL() {
Node *tmp = first;
while (tmp != NULL) {
cout << tmp->count <<\":\"<<tmp->word << endl;
tmp = tmp->next;
}
}
void LLSE::addFirst(string w) {
first = new Node(w);
last = first;
size = 1;
}
void LLSE::insertUnique(string w) {
Node *tmp = first;
if (tmp == NULL) {
addFirst(w);
}
else {
while (tmp != NULL && tmp->word < w) {
tmp = tmp->next;
}
if ((tmp!= NULL) && (tmp->word == w)) {
tmp->count++;
}
else {
Node *tmp2 = new Node(w);
if (tmp != NULL) {
if (tmp->prev != NULL) {
tmp->prev->next = tmp2;
tmp2->prev = tmp->prev;
}
else {
first = tmp2;
}
tmp2->next = tmp;
tmp->prev = tmp2;
}
else {
last->next = tmp2;
tmp2->prev = last;
last = tmp2;
}
size++;
}
}
}
// Write an insertion Sort on the linked list (not an array,
// a linked list!
void LLSE::insertionSortLL() {
}
// Convert the linked list to an array of nodes and return that array
Node *LLSE::convertToArray() {
}
// For the quicksort - the partition
int LLSE::partition(int beg,int end) {
}
// your recursive quicksort
void LLSE::quickSort( int beg, int end) {
}
//Take the linked list and create a binary heap
Node *LLSE::makeHeap() {
}
//Sort the heap array using heapsort
void LLSE::heapSort() {
}
#include \"Node.hpp\"
#include <iostream>
#include <string>
using namespace std;
Node::Node(string s) {
count = 1;
next = NULL;
prev = NULL;
word = s;
}
#ifndef NODE_HPP_
#define NODE_HPP_
#include <iostream>
#include <string>
using namespace std;
class Node {
friend class Document;
friend class LLSE;
Node *next;
Node *prev;
int count;
string word;
public:
Node(string w);
Node();
};
#endif /* NODE_HPP_ */
Solution
Write an insertion Sort on the linked list (not an array,
// a linked list!
// function to sort linked list using insertion sort
void insertionSortLL (struct node **head_referenceerence)
{
// Initialize sorted linked list
struct node *sorted = NULL;
// Traverse the given linked list and insert every
// node to sorted
struct node *current = *head_referenceerence;
while (current != NULL)
{
// Store next for next iteration
struct node *next = current->next;
// insert current in sorted linked list
sortedInsertsort(&sorted, current);
// Update current
current = next;
}
// Update head_referenceerence to point to sorted linked list
*head_referenceerence = sorted;
}
/* function to insert a new_node in a list.
*/
void sortedInsertsort(struct node** head_referenceerence, struct node* new_node)
{
struct node* current;
/* Special case for the head end */
if (*head_referenceerence == NULL || (*head_referenceerence)->data >= new_node->data)
{
new_node->next = *head_referenceerence;
*head_referenceerence = new_node;
}
else
{
/* Locate the node before the point of insertion */
current = *head_referenceerence;
while (current->next!=NULL &&
current->next->data < new_node->data)
{
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
Convert the linked list to an array of nodes and return that array
convertToArray() {
String[] array = linkedlist.toArray(new String[linkedlist.size()]);
//Displaying Array content
cout << \"Array Elements:\";
for (int i = 0; i < array.length; i++)
{
cout << array[i];
}
}
// For the quicksort - the partition
int LLSE::partition(int beg,int end) {
}
// your recursive quicksort
void LLSE::quickSort( int beg, int end)
struct node *getlastelement(struct node *cur)
{
while (cur != NULL && cur->next != NULL)
cur = cur->next;
return cur;
}
// Partitions the list taking the last element as the pivot
struct node *partition(struct node *head, struct node *end,
struct node **newHead, struct node **newEnd)
{
struct node *pivot = end;
struct node *prev = NULL, *cur = head, *tail = pivot;
// During partition, both the head and end of the list might change
// which is updated in the newHead and newEnd variables
while (cur != pivot)
{
if (cur->data < pivot->data)
{
// First node that has a value less than the pivot - becomes
// the new head
if ((*newHead) == NULL)
(*newHead) = cur;
prev = cur;
cur = cur->next;
}
else // If cur node is greater than pivot
{
// Move cur node to next of tail, and change tail
if (prev)
prev->next = cur->next;
struct node *tmp = cur->next;
cur->next = NULL;
tail->next = cur;
tail = cur;
cur = tmp;
}
}
// If the pivot data is the smallest element in the current list,
// pivot becomes the head
if ((*newHead) == NULL)
(*newHead) = pivot;
// Update newEnd to the current last node
(*newEnd) = tail;
// Return the pivot node
return pivot;
}
//here the sorting happens exclusive of the end node
struct node *quickSort(struct node *head, struct node *end)
{
// base condition
if (!head || head == end)
return head;
node *newHead = NULL, *newEnd = NULL;
// Partition the list, newHead and newEnd will be updated
// by the partition function
struct node *pivot = partition(head, end, &newHead, &newEnd);
// If pivot is the smallest element - no need to recur for
// the left part.
if (newHead != pivot)
{
// Set the node before the pivot node as NULL
struct node *tmp = newHead;
while (tmp->next != pivot)
tmp = tmp->next;
tmp->next = NULL;
// Recur for the list before pivot
newHead = quickSort(newHead, tmp);
// Change next of last node of the left half to pivot
tmp = getlastelement(newHead);
tmp->next = pivot;
}
// Recur for the list after the pivot element
pivot->next = quickSort(pivot->next, newEnd);
return newHead;
}
// The main function for quick sort. This is a wrapper over recursive
// function quickSorting()
void quickSorting(struct node **headRef)
{
(*headRef) = quickSort(*headRef, getlastelement(*headRef));
return;
}
//Take the linked list and create a binary heap
// converts a given linked list representing a complete binary tree into the
// linked representation of binary tree.
void makeHeap (ListNode *head, BinaryTreeNodee* &root)
{
// queue to store the parent nodes
queue<BinaryTreeNodee *> q;
// Base Case
if (head == NULL)
{
root = NULL; // Note that root is passed by reference
return;
}
// 1.) The first node is always the root node, and add it to the queue
root = newBinaryTreeNodee(head->data);
q.push(root);
// advance the pointer to the next node
head = head->next;
// until the end of linked list is reached, do the following steps
while (head)
{
// 2.a) take the parent node from the q and remove it from q
BinaryTreeNodee* parent = q.front();
q.pop();
// 2.c) take next two nodes from the linked list. We will add
// them as children of the current parent node in step 2.b. Push them
// into the queue so that they will be parents to the future nodes
BinaryTreeNodee *leftChildren = NULL, *rightChildren = NULL;
leftChildren = newBinaryTreeNodee(head->data);
q.push(leftChildren);
head = head->next;
if (head)
{
rightChildren = newBinaryTreeNodee(head->data);
q.push(rightChildren);
head = head->next;
}
// 2.b) assign the left and right children of parent
parent->left = leftChildren;
parent->right = rightChildren;
}
}
//Sort the heap array using heapsort
