Answer in C++, Fully Commented. Question 3 (12 marks) Purpose: To practice using
ID: 3686539 • Letter: A
Question
Answer in C++, Fully Commented.
Question 3 (12 marks)
Purpose: To practice using search and sort. 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.
Task 3
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:
Your program in a text file called a9q3.cpp.
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.
//============================================================================
// Name : A9Q3_skeleton.cpp
// Author : Jeff Long
// Description : Basic skeleton provided as starting point for A9Q3, CMPT 111
//============================================================================
#include <iostream>
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
//============================================================================
// Name : A9Q3_skeleton.cpp
// Author : Jeff Long
// Description : Basic skeleton provided as starting point for A9Q3, CMPT 111
//============================================================================
#include <iostream>
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)
{
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)
{
if(d1.year < d2.year)
return true;
else if(d1.year == d2.year){
if(d1.month < d2.month)
return true;
else 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)
{
// using selection sort
for(int i=0; i<size; i++){
int min_index = i;
for(int j=i+1; j<size; j++)
if(before(d[j], d[min_index]))
min_index = j;
// swaping
Date temp = d[i];
d[i] = d[min_index];
d[min_index] = 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)
{
for(int i=0; i<size; i++){
if(equal(target, darray[i]))
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)
{
int l=0, r=size-1;
while(l <= r){
int m = (l+r)/2;
if(equal(target, darray[m]))
return true;
if(before(darray[m], target))
l = m;
else
r = m;
}
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);
// calling sort
sort(dateArray, 6);
cout<<" After sorting: ";
printDateArray(dateArray, size);
//searching
Date date = {17, 7, 2012};
cout<<" Using BinarySearch - {17, 7, 2012} avalilable ?: "<<binarySearch(date, dateArray, 6)<<endl;
cout<<" Using LinearSearch - {17, 7, 2012} avalilable ?: "<<linearSearch(date, dateArray, 6)<<endl;
return 0;
}
/*
Output:
January 1 2015
January 30 2015
November 15 2014
June 2 2015
July 17 2012
January 1 1
After sorting:
January 1 1
July 17 2012
November 15 2014
January 1 2015
January 30 2015
June 2 2015
Using BinarySearch - {17, 7, 2012} avalilable ?: 1
Using LinearSearch - {17, 7, 2012} avalilable ?: 1
*/