# Sorting Algorithms Solution

\$30.00

Category:

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

• Selection-Sort

• Insertion-Sort

• Standard Template Sort of a vector<int>

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.

In addition to sorting an array of random integers, you will also be required to sort a linked-list of random integers using the Insertion Sort (modified to sort a linked list instead of an array. see pseudo-code at end of document)

Lastly, you will build a vector<int> with the same random data as your array and use the std::sort() to sort the vector. This part should be really easy and fast! A good example of how to do this is at http://en.cppreference.com/w/cpp/algorithm/sort

• Create a Sort Class
o Member variables
◦ dynamic array of ints

◦ size of

◦ vector<int>

◦ random seed value

o Constructor(array size) o Destructor

◦ friend ostream& operator<< (ostream& out, const Sort& s)
• for testing

• (you don’t really need this but I want you to have practice with this operator) o Insertion Sort  You need to write all of this.
o Insertion Sort of a linked list  You need to write all of this.

o Selection Sort  In book pg. 634 – pay attention to the swap() function you need to write.

o Merge Sort  in book pg. 646; 650 – you just need to copy this. (or write your own ) o Quick Sort  In book pg. 656 – you still need to write partition().

• Quick Sort and partition should be separate functions.

◦ With quicksort calling partition

◦ Also you need to follow the pseudo-code from the book

o VectorSort using std::sort() (should be one line of code)
◦ http://en.cppreference.com/w/cpp/algorithm/sort

o A function to initialize the array with random integers

◦ use the same seed before each array initialization, so the array is always the same

o A function to initialize the linked list with random integers

• use the same seed before each array initialization, so the array is always the same

o A function to initialize a vector<int> with random integers

◦ again, use the same seed before each array initialization, so the array is always the same

o You will also need several helper functions.
▪ These should be private.

• Create a non-interactive driver that runs each of these sorts and times and displays the outputs.

Documentation (10 pts)

Student name, Section and Disclaimer Proper function and class headers
______/5
______/5

Sort Class (75 pts)
Appropriate private data members
______/5
Interface functions
Constructor/Destructor
Operators

array, list, vector initialization
Insertion Sort

Selection Sort
Quick Sort
Partition
Merge Sort
Merge
std::sort() of vector<int>

______/10
______/5
______/5
______/5

______/10
______/5
______/5

______/10
______/5
______/5
______/5

Driver (30 pts)
Non-interactive driver
Output displayed correctly
All interface functions used
Timer class used
Correct output

______/5
______/5
______/5

______/15

Insertion Sort of a Linked List (pseudo code)

2. make a new temp linked list (initially empty)
3. remove front of unsorted list and insert it into the proper location in the temp list