Description

5/5 - (2 votes)

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.