Question 3 (12 marks) Purpose: To practice using search and sort in C++. To prac

Question

Question 3 (12 marks)

Purpose: To practice using search and sort in C++. To practice implementing algorithms from a textbook.

For this problem, you will implement searching and sorting algorithms from the textbook. The only real challenge is that you will be searching and sorting using a Record type for representing calendar Dates, as opposed to using atomic data like integers or floats. Mostly, you will be able to use the relevant algorithms exactly as they are presented in the text, with just a few tweaks to suit the needs of this assignment.

You should use A9Q3start.cpp as a starting point for this question.

Task 1

Implement the equal() and before() functions from the skeleton program. equal() checks whether two dates, d1 and d2, are exactly equal to one another. You can do this by comparing the three individual fields of the Date record type. before() checks whether the date d1 comes chronologically before the date d2.

Before going on, do some testing of your own to make sure these functions are working. But you don't need to hand in the testing for these two functions.

Task 2

Implement the sort() function from the skeleton program. It should sort the given array of Dates in ascending chronological order. To do this, implement one of the three sorting algorithms (insertion, selection or bubble) in the textbook. The choice of which sort to use is up to you.

Because you are sorting an array of Dates (instead of ints or floats), you should find that you need to use the functions you wrote for Task 1 to complete your sort.

Once you are done, test your sorting function using two different Date arrays, each with at least 10 elements. Copy/paste the results of this testing into your testing document for submission.

Implement the linearSearch() and binarySearch() functions from the skeleton program. Again, you may use the textbook as a starting point for these algorithms. Your binary search function may assume that the input array is already sorted (that's why you needed to do Task 2 before Task 3, even though sorting is probably more complicated than searching).

As per before, you will likely find the functions you wrote for Task 1 very useful here.

Once you are done, test both of your search functions with one input array and five different target dates. 3 of the target dates should actually be in the array (i.e. you expect your search function to return 'true') and 2 of the target dates should *not* be in the array (i.e. you expect your search function to return false). Copy/paste these tests into your testing document.

What to hand in:

1. Your program in a text file called a9q3.cpp.

2. A testing file called a9q3_results.txt (.rtf, .pdf and .doc are also okay). It should show your testing for Tasks 2 and 3 above.

This is the skeleton A9Q3start.cpp :

#include
using namespace std;

///////////////////////////////////////////////////////////////
// You shouldn't need to change the following.
///////////////////////////////////////////////////////////////

struct Date {
   int day;
   int month;
   int year;
};

void printDate(Date d)
{
   string monthnames[12] = {"January", "February", "March", "April", "May", "June",
                           "July", "August", "September", "October", "November", "December"};
   cout << monthnames[d.month-1] << " " << d.day << " " << d.year;
}

void printDateArray(Date d[], int size)
{
   for (int i = 0; i < size; i = i + 1)
   {
       printDate(d[i]);
       cout << endl;
   }
}

//////////////////////////////////////////////////////////////////
// Your work will be below this line
//////////////////////////////////////////////////////////////////

// Returns true if d1 and d2 represent the same date, and false otherwise
bool equal(Date d1, Date d2)
{
   // TODO: write this function
   return false;
}

// Returns true if the date d1 is before d2, and false otherwise
bool before(Date d1, Date d2)
{
   // TODO: write this function
   return false;
}

// sorts in ascending order the array of Dates d with the given size
void sort(Date d[], int size)
{
   // TODO: complete this function with the sorting algorithm of your choice
}

// returns true if the target Date exists in darray and false otherwise
// linear search is used to search the array
bool linearSearch(Date target, Date darray[], int size)
{
   // TODO: complete this function
   return false;
}


// returns true if the target Date exists in darray and false otherwise
// darray is assumed to be sorted in ascending order
// binary search is used to search the array
bool binarySearch(Date target, Date darray[], int size)
{
   // TODO: complete this function. You are allowed to change the function header
   // if you prefer to implement the recursive version of binary search
   return false;
}


int main() {

   // A basic array of Dates for quick testing. You can modify and expand this to
   // make your tests more rigorous
   int size = 6;
   Date dateArray[6] = { {1, 1, 2015}, {30, 1, 2015}, {15, 11, 2014}, {2, 6, 2015},
           {17, 7, 2012}, {1, 1, 1}};

   printDateArray(dateArray, size);


   return 0;
}

Explanation / Answer

#include <string>
#include <iostream>
#include <fstream>
using namespace std;

///////////////////////////////////////////////////////////////
// You shouldn't need to change the following.
///////////////////////////////////////////////////////////////

struct Date {
int day;
int month;
int year;
};

void printDate(Date d)
{
string monthnames[12] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
cout << monthnames[d.month-1] << " " << d.day << " " << d.year;
}

void printDateArray(Date d[], int size)
{
for (int i = 0; i < size; i = i + 1)
{
printDate(d[i]);
cout << endl;
}
}

//////////////////////////////////////////////////////////////////
// Your work will be below this line
//////////////////////////////////////////////////////////////////

// Returns true if d1 and d2 represent the same date, and false otherwise
bool equal(Date d1, Date d2)
{
// TODO: write this function
if (d1.day == d2.day && d1.month == d2.month && d1.year == d2.year )
{
return true;
}
return false;
}

// Returns true if the date d1 is before d2, and false otherwise
bool before(Date d1, Date d2)
{
// TODO: write this function
if(d1.year < d2.year) return true;
if(d1.year == d2.year) if(d1.month < d2.month) return true;
if(d1.year == d2.year) if(d1.month == d2.month) if (d1.day < d2.day) return true;

return false;
}

// sorts in ascending order the array of Dates d with the given size
void sort(Date d[], int size)
{
Date temp;
// TODO: complete this function with the sorting algorithm of your choice
for (int i = 0; i < size; ++i)
{
for (int j = i+1; j < size; ++j)
{
if (before(d[j],d[i]) == true)
{
temp = d[i]; //swapping entire struct
d[i] = d[j];
d[j] = temp;
}
}
}
}

// returns true if the target Date exists in darray and false otherwise
// linear search is used to search the array
bool linearSearch(Date target, Date darray[], int size)
{
// TODO: complete this function
for (int i = 0; i < size; ++i)
{
if(darray[i].day == target.day && darray[i].month == target.month && darray[i].year == target.year) return true;
}
return false;
}

// returns true if the target Date exists in darray and false otherwise
// darray is assumed to be sorted in ascending order
// binary search is used to search the array
bool binarySearch(Date target, Date darray[], int size)
{
// TODO: complete this function. You are allowed to change the function header
// if you prefer to implement the recursive version of binary search
int low=0,high=size-1, middle;
while (low <= high)
{
middle = (low + high)/2;
if ( equal(darray[middle],target) == true )
return true;
else if ( before(target,darray[middle]) == true )
high = middle -1;
else
low = middle +1;
}
return false;
}

int main() {

// A basic array of Dates for quick testing. You can modify and expand this to
// make your tests more rigorous
int size = 6;
Date dateArray[6] = { {1, 1, 2015}, {30, 1, 2015}, {15, 11, 2014}, {2, 6, 2015},
{17, 7, 2012}, {1, 1, 1}};

printDateArray(dateArray, size);
sort(dateArray,size);
cout << endl;
cout << "After sorting" << endl;
printDateArray(dateArray, size);
cout << endl;
Date d = {1,1,2015};
if( linearSearch(d, dateArray,size) == true )
cout << "linearSearch: Date is found " << endl;
else
cout << "linearSearch: Date is not present " << endl;

if( binarySearch(d, dateArray,size) == true )
cout << "binarySearch: Date is found " << endl;
else
cout << "binarySearch: Date is not present " << endl;

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.