Project #5 Sorting Algorithms

$35.00

Description

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 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

• Member variables

o dynamic array of integers o sizeof

Constructor(array size)

• Destructor

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

• Selection Sort or the array data ovoid SelectionSortO;

• Insertion Sort of the array data ovoid InsertionSortO;

• Merge Sort of the array data ovoid MergeSortO;

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

• You will also need several helper functions.

• These should be private.

• void MergeSortRecursionHelper(intindexl, intindexK);

• void QuickSortRecursionHelper(intinitiaILowlndex, intinitiaIHighlndex);

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.