Your cart is currently empty!
Purpose to familiarize you with: Sorting Algorithms Recursion Analysis The purpose of this lab is to demonstrate the speed difference between sorting arrays of random integers using: Quick-Sort Merge-Sort Insertion Sort Selection-Sort Built-in Sort of an array (from <algorithm» This difference will not show if the array size is too small. Therefore, you should…
Purpose
to familiarize you with:
Recursion
The purpose of this lab is to demonstrate the speed difference between sorting arrays of random integers using: Quick-Sort
Merge-Sort Insertion Sort Selection-Sort
Built-in Sort of an array (from <algorithm»
This difference will not show if the array size is too small. Therefore, you should make your array as large as possible (without having it take too long), and still have 2 significant digits of output for each search. Quick and Merge are much faster than Insertion and Selection. You also need to re-randomize each time to give accurate results for each sort.
Lastly, you will use the std::sortO to sort the array. This part should be easy and fast’ A good example of how to do this is at http://www.cplusplus.com/articles/NhAORXSz/
Tasks
Create a Sort Class
o dynamic array of integers o sizeof
Constructor(array size)
A function to get the size of the array oint GetSizeO const;
A function to return the array of integers
oint *GetDataArrayO const;
A function to initialize the array with random integers ovoid InitArrayO;
o use the same seed before each array initialization, so the array is always the same
Quick Sort of the array data ovoid QuickSortO;
o Quick Sort and partition should be separate functions.
o With QuickSortO calling PartitionO
std::sortO (should be one line of code)
ovoid AlgorithmSortO;
o http://en.cpprererence.com/w/cpp/algorithm/sort
Create a non-interactive driver that runs each of these sorts and times and displays the outputs.
starting SelectionSort
Selection Sort duration: 10821ms.
starting InsertionSort
Insertion Sort duration: 11459ms.
starting MergeSort
erge Sort duration: 246ms.
starting QuickSort
Quick Sort duration: 210ms.
starting std: :sort()
std: :sort() duration of: 164ms.
Use the provided Timer.cpp and Timer.h as you did in the Search Project to time these sorts. Again, adjust the size of the array so that you have at least two significant digits of time data.