Description
Overview
In this assignment, the student will write a C++ program that heuristically compares the execution time of bubble sort, selection sort, and insertion sort using file sizes of various input sizes.
When completing this assignment, the student should demonstrate mastery of the following concepts:
· Sorting Algorithms – Bubble Sort
· Sorting Algorithms – Selection Sort
· Sorting Algorithm – Insertion Sort
· Timers – Fast Clock
· Heuristic Algorithm Analysis
· Object Composition
· File I/O
· Dynamic Memory and Stack Limitations
Assignment
In this assignment, you will be writing two objects to heuristically compare the performance of the bubble sort, selection sort, and insertion sort algorithms. To do this, a “Timer” object will be created and compositionally related to a storage class that will load the file contents, execute the sorts in an unbiased manner, handle any memory allocations that need to be made in order to do this, and report back the execution times of each algorithm on the provided input files for that machine.
First you will need to make a Timer object. This object should function like a traditional stopwatch with methods for starting, stopping, resetting, and reporting back times. The design of the object itself is up to you (it should minimally contain methods for the aforementioned ideas), but it must consist of a solitary object that provides interfaces appropriate for being compositionally included as part of a sorting object to facilitate the time keeping portion of this exercise. Make sure you have a properly separated specification and implementation file for your Timer/Stopwatch object.
The second object you will make should be a data housing object that has methods that enable client code to read in the formatted contents of data files, house the data in memory, and execute bubble sort, selection sort, and insertion sort algorithms in a timed fashion with the assistance of your Timer object. You will need to include interfaces/methods for providing file names, reporting erroneously formatted data files, reporting files sizes, initiating individual sort algorithms, and reporting back unbiased times to the client code.
There are a number of memory considerations that you need to make when constructing the “data housing” object as well. When an array is declared in
a function, the memory for that array is automatically placed on the frame associated with that function. Many compilers have natural limits for the size a given stack frame can consume, so large arrays will cause problems. Arrays the require large numbers of indexes (maybe millions), the information must be placed on the stack and accessed accordingly. When reading your data files, first parse them to determine their length, allocate the needed amount of space on the heap for that particular file’s array, and make sure you deallocate all heap-based allocations properly before the test completes.
Finally, you must create a driver that instantiates your object, loads the files, and executes the sorts, and reports back the times back in a manner similar to the following screenshot.
Madison Hayes –
“Thank u! Really good!!”