I was assigned to create a merge sort method using doubly link lists instead of
ID: 3821051 • Letter: I
Question
I was assigned to create a merge sort method using doubly link lists instead of an array. There is a quicksort function i have completed to test runtimes. The purpose of the the assignment is to finish the merge() and split() function using the values and data already given. These function headers cannot be changed.
The code is as follows:
driver.cpp ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
//#include <list>
#include "linkedList.h"
#include <algorithm>
#include <ctime>
using namespace std;
//Pick a pivot (try just the first item for example). Partition the array items in the range from index s to index e by
//moving all items smaller than the pivot to the left of the pivot,
//and all items large to the right, with the pivot in between. Return the index of the pivot item after this partitioning.
//To ensure a good average case run time regardless of input order, how should you choose the pivot?
template <class T>
unsigned partition(T * A, int s, int e)
{
int pivot = s;
for (int j = s + 1; j < e; j++)
{
if (A[j] <= A[s])
{
pivot++;
swap(A[pivot], A[j]);
}
}
swap(A[pivot], A[s]);
return pivot;
}
template <class T>
void quickSort(T * A, int start, int end)
{
if( start < end )
{
int p=partition(A, start, end);
quickSort(A, start, p - 1);
quickSort(A, p+1, end);
}
}
int main()
{
unsigned size = 6;
//part 1: implement a merge sort for a doubly linked list class
linkedList<unsigned> numbers;
for (int i = 0; i < size; i++)
numbers.push_back(rand() + rand()*pow(2, 15));
clock_t startTime = clock();
numbers.mergeSort();
clock_t endTime = clock();
numbers.display();
cout << "Merge sort took: " << (endTime - startTime) / (double)CLOCKS_PER_SEC << " seconds." << endl;
//part 2: implement a quick sort to sort an array.
unsigned * A = new unsigned[size];
for (int i = 0; i < size; i++)
A[i] = rand()+rand()*pow(2,15); //test also with: A[i] = i;
startTime = clock();
quickSort(A, 0, size - 1);
endTime = clock();
/*
for (int i = 0; i < size; i++)
cout << A[i] << endl;
*/
cout << "Quick sort took: " << (endTime - startTime) / (double)CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
linkedList.h ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
using namespace std;
template <class T>
class linkedList
{
private:
class node
{
public:
T data;
node * next;
node * prev;
node(T x)
{
data = x;
next = NULL;
prev = NULL;
}
};
node * head;
node * tail;
int numItems;
// THIS NEEDS CHANGE
void split(node * h, node * t, node * t1, node * h2) // header does not change.
{
t1 = h;
for (int i = 0; i < (numItems / 2) - 1; i++)
t1 = t1->next;
h2 = t1->next;
}
// THIS NEEDS CHANGE
void merge(node * h, node * t1, node * h2, node * t) // header cannot be changed.
{
node * TH = NULL, *TT = NULL;
while (h2 != t->next && h != t1->next)
{
if (h->data < h->data)
{
if (TH == NULL)
TH = h;
else
{
TT->next = h;
TT->next->prev = TT;
TT = TT->next;
}
}
if (h->data > h2->data)
{
if (TH == NULL)
TH = h2;
else
{
TT->next = h2;
TT->next->prev = TT;
TT = TT->next;
}
h2 = h2->next;
}
}
}
//merge sort the list from node h to t
void mergeSort(node * &h, node * &t) //header cannot be changed.
{
if (h != NULL && h != t) //2 or more items, otherwise base case of nothing
{
//step 1: split list into 2
//point t1 and h2 to nodes such that:
//the left half of the list is from node h to t1, right half from node h2 to t
node * t1;
node * h2;
split(h, t, t1, h2);
//step 2: sort 2 halves
mergeSort(h, t1);
mergeSort(h2, t);
//step 3: merge sorted halves back together
//into a single sorted list
merge(h, t1, h2, t);
}
}
//CANNOT CHANGE
public:
linkedList()
{
head = NULL;
tail = NULL;
numItems = 0;
}
//frees all dynamically allocated memory (the nodes in the list)
~linkedList()
{
while (!empty())
{
pop_front();
}
}
int size()
{
return numItems;
}
//add item x to back of list
void push_back(T x)
{
numItems++;
if (head == NULL)
{
head = new node(x);
tail = head;
}
else
{
tail->next = new node(x);
tail->next->prev = tail;
tail = tail->next;
}
}
//remove and return the first item in the list
T pop_front()
{
numItems--;
T output = head->data;
if (head == tail)
{
delete head;
head = NULL;
tail = NULL;
}
else
{
head = head->next;
delete head->prev;
head->prev = NULL;
}
return output;
}
void display()
{
node * c = head;
while (c != NULL)
{
cout << c->data << ",";
c = c->next;
}
cout << endl;
}
bool empty()
{
return (numItems == 0);
}
void mergeSort()
{
mergeSort(head,tail);
}
};
Explanation / Answer
#include<iostream>
#include<assert.h>
using namespace std;
class node
{
public:
node* create(int n);
void Insert(node** head,int n);
void print(node* head);
node* merge(node** head1,node ** head2,node** bar);
private:
node* next;
node* prev;
int data;
};
node* node::create(int n)
{
node* temp=new node;
assert(temp);
temp->data=n;
temp->next=NULL;
temp->prev=NULL;
return temp;
}
void node::Insert(node** head,int n)
{
node* temp=create(n);
if(*head==NULL)
{
*head=temp;
}
else
{
node* foo=(*head);
while(foo->next!=NULL)
{
foo=foo->next;
}
foo->next=temp;
temp->prev=foo;
}
}
node* node::merge(node** head1,node** head2,node** result)
{
//node* foo=NULL;
node* list=*head2;
node* pass=*head1;
if(*head1==NULL)
{
return *head2;
}
else if(*head2==NULL)
{
return *head1;
}
while((*head1)->next!=NULL || (*head2)->next!=NULL)
{
jump:
if((*head1)->data < (*head2)->data){
Insert(result,(*head1)->data);
(*head1)=(*head1)->next;
goto jump;
}
else if((*head1)->data > (*head2)->data){
Insert(result,(*head2)->data);
(*head2)=(*head2)->next;
goto jump;
}
else if((*head1)->data == (*head2)->data){
Insert(result,(*head1)->data);
(*head1)=(*head1)->next;
(*head2)=(*head2)->next;
goto jump;
}
}
return *result;
}
void node::print(node* head)
{
node* temp=head;
if(head==NULL)
{
cout<<"List is Empty! ";
}
while(temp!=NULL)
{
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<endl;
}
int main()
{
node*head1=NULL,*head2=NULL,*res=NULL;
int m,n;
node ni;
cout<<"Enter size of node 1 ?";
cin>>n;
cout<<"Enter node 1 ? ";
for(int i=0;i<n;++i)
{
cout<<"Enter element ?";
cin>>m;
ni.Insert(&head1,m);
}
cout<<"Enter size of node 2?";
cin>>n;
cout<<"Enter node 2 ? ";
for(int i=0;i<n;++i)
{
cout<<"Enter element ?";
cin>>m;
ni.Insert(&head2,m);
}
cout<<"Print node 1 : ";
ni.print(head1);
cout<<"Print node 2 : ";
ni.print(head2);
res=ni.merge(&head1,&head2,&res);
ni.print(res);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.