C++ Create a data structure that keeps track of templated data types in a sorted array. Objects should be sortable by containing at least one sortable property (e.g. item for sale { price, size }, books { author, title, genre }, etc.) and implementing the less than “.
C++
Create a data structure that keeps track of templated data types in a sorted array. Objects should be sortable by containing at least one sortable property (e.g. item for sale { price, size }, books { author, title, genre }, etc.) and implementing the less than “<” and equals “==” operator overloads. The data structure should use an array of the templated types for the purpose of this assignment (don’t use a Vector). Implement a search function that will return:
•Object with the searched property (if any)
•Additional suggestions (similar objects to the one searched)
•Rankings of most likely to least likely results (display at least 3 results)
You will also need to provide a Big-O analysis of your algorithms.
Grading Criteria:
•[2 Points] At least two different objects with at least one sortable property
•Sortable Objects class:
o[2 Points] Less than operator overload “<”
o[2 Points] Equals operator overload “==”
o[2 Points] << operator overload to give a string representation of the instance
•Data Structure class (must be templated and must use array):
o[2Points] Insert must result in sorted array (i.e. you’ll need to shuffle things over)
o[2Points] Remove must not leave gaps in sorted array (same with insert, you’ll need to shuffle things over)
•Search method given a property to search for:
§[1Point] Returns the first instance that meets the searched criteria, if any
§[1Point] Returns an instance of the most similar object to thesearched property if an exact match isn’t found
•Search method for top 3 results
§[2Points] Returns at least 3 unique results don’t return multiple instances of the same object)
§[2 Points] Rankings of most likely to least likely results (if an object with the exact property is found, that’s rank #1. Otherwise, you determine what the “closest”rank is).
o[2 Points] << operator overload to print out instances in the array
•Driver:
o[2Points] Demonstrate inserting minimum of 5 instances of one object out-of-order and show that it is in-order subsequently
o[1 Point] Demonstrate inserting another instance of an object that is equals to an object that already exist in the data structureand show that it is in the correct order subsequently
o[1Point] Demonstrate searching for an object that exist
o[1 Point] Demonstrate searching for an object that doesn’t exist
o[1 Point] Demonstrate searching for top 3 resultsfor an object that exist (the found object should be rank 1)
o[1 Point] Demonstrate searching fortop 3 results for an object that doesn’t exist
o[1 Point] Demonstrate array is still in order after a remove operation
•Big-O Analysis:
o[1Point] What is the Big-O of your search algorithm?
o[1 Point] What is the Big-Oof your insert algorithm?
•Extra Credit:
o[2 Points] Search algorithm that has O(log n) complexity