CSCI 335 Fall 2021 HW 4: Sorting Sort.h (code from sorting routines in Chapter 7)

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

I need help with an assignment

 

CSCI 335 Fall 2021

HW 4: Sorting

108 points (63 autograder + 45 style, design, documentation)

 

This is an individual assignment

In this assignment you are going to compare various sorting algorithms. You will also

modify the algorithms in order for a Comparator class to be used for comparisons. You will

then further experiment with algorithmic variations.

Code Files provided:

1. Sort.h (code from sorting routines in Chapter 7)

2. test_sorting_algorithms.cc

Question 1 (80 points)

******** Step 1 ********* (10 points)

You should write a small function that verifies that a collection is in sorted order.

template<typename Comparable, typename Comparator>

bool VerifyOrder(const vector<Comparable> &input, Comparator less_than)

The above function should return true if and only if the input is in sorted order according to

the Comparator. For example, in order to check whether a vector of integers (vector<int>

input_vector) is sorted from smaller to larger, you need to call:

VerifyOrder(input_vector, less<int>{});

If you want to check whether the vector is sorted from larger to smaller you need to call

VerifyOrder(input_vector, greater<int>{});

This function should be placed inside test_sorting_algorithms.cc

All deliverables are described at the end of the file.

Next, you should write two functions, one that generates a random vector, and another that

generates a sorted vector. The sorted vector should generate a vector of increasing or

decreasing values based on bool smaller_to_larger. You will use both of these for your

own testing purposes.

The function signatures should be as follows.

1) vector<int> GenerateRandomVector(size_t size_of_vector)

2) vector<int> GenerateSortedVector(size_t size_of_vector, bool

smaller_to_larger)

Note: Look at the TestTiming() and ComputeDuration()functions given to you in

test_sorting_algorithms.cc.

This will show you the way to compute the duration in nanoseconds of a

piece of code when it runs.

Please comment out the TestTiming() function before you submit. You should

keep the ComputeDuration() function.

******** Step 2 ********* (70 Points)

You will now modify several sorting algorithms provided to you in Sort.h. You will modify:

HeapSort, MergeSort, and QuickSort.

You should modify these algorithms so that they each take a Comparator with their

input.

The signatures for these sorts should be (see file Sort.h where the signatures are provided):

template <typename Comparable, typename Comparator>

void HeapSort(vector<Comparable> &a, Comparator less_than)

template <typename Comparable, typename Comparator>

void MergeSort(vector<Comparable> &a, Comparator less_than)

template <typename Comparable, typename Comparator>

void QuickSort(vector<Comparable> &a, Comparator less_than)

You will have to modify multiple functions, helpers and wrappers to make this fully

operational without error.

These functions should be modified and kept inside Sort.h

******** Step 3 *********

Now that those two steps are finished, you will move on to testing.

You should now create a driver program, within test_sorting_algorithms.cc (initial

version given to you), that will test each of your modified sorts with different inputs.

The program will be executed as follows:

./test_sorting_algorithms <input_type> <input_size> <comparison_type>

where <input_type> can be random, sorted_small_to_large, or

sorted_large_to_small, <input_size> is the number of elements of the input, and

<comparison_type> is either less or greater.

For example, you should be able to run

./test_sorting_algorithms random 20000 less

The above should produce a random vector of 20000 integers, and apply all three algorithms

using the less<int>{} Comparator.

You can also run for example:

./test_sorting_algorithms sorted_small_to_large 10000 greater

The above will produce the vector of integers containing 1 through 10000 in that order, and

will test the three algorithms using the greater<int>{} Comparator.

This driver should be implemented inside the testSortingWrapper() function.

The formatting for driver output is shown at the bottom of the file.

Note: The format presented is an example for how you should test your functions. It serves

as a good base of understanding of how the different sorts will vary in runtime, with different

types of inputs. You will not be constrained (or graded exactly on how) you implement this

step, but doing so would help you and us verify the accuracy of your work. (You still must

create a driver that functions like the one described, but it will not be autograded for

formatting, it will be manually looked at.)

Question 2 (28 points)

In this question, you will implement variations of the quicksort algorithm. You will

investigate the following pivot selection procedures.

1. a) Median of three (already implemented in part 2)

2. b) Middle pivot (always select the middle item in the array)

3. c) First pivot (always select the first item in the array)

Although median of three is already implemented in the file, you will use it for comparisons

further in this question.

The following two quicksort implementations, middle pivot, and first pivot, should have

wrappers with the following signatures that then call the full implementations (see Sort.h).

//Middle Pivot Wrapper

template <typename Comparable, typename Comparator>

void QuickSort2(vector<Comparable> &a, Comparator less_than)

//First Pivot Wrapper

template <typename Comparable, typename Comparator>

void QuickSort3(vector<Comparable> &a, Comparator less_than)

Note: these are just the wrappers, you have to write the actual quicksort

functionality in another function called by these (similar as in the original quicksort

provided).

In order to test these functions, you will add to the output of the driver

described in Step 3. The full format is shown below deliverables.

Deliverables: You should submit these files:

● README file

● Sort.h (modified)

○ All sort modifications and additions should be kept within this file.

● test_sorting_algorithms.cc (modified)

○ VerifyOrder()

○ GenerateRandomVector()

○ GenerateSortedVector()

○ testSortingWrapper()

Note: A large amount of this assignment will be manually checked and graded. We will run

your sorts and implemented functions in the autograder, but the sort modifications will be

verified manually.

Driver Formatting

The full driver format should be as follows: (example shown with function call

./test_sorting_algorithms random 20000 less) Note: The number output

next to “Verified” is the boolean output of the function VerifyOrder(). If that

value is 0, your sort did not work as intended.

Running sorting algorithms: random 20000 less

Heapsort

Runtime: <X> ns

Verified: 1

MergeSort

Runtime: <X> ns

Verified: 1

QuickSort

Runtime: <X> ns

Verified: 1

Testing Quicksort Pivot Implementations

Median of Three

Runtime: <X> ns

Verified: 1

Middle

Runtime: <X> ns

Verified: 1

First

Runtime: <X> ns

Verified: 1 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of