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

o also for a linked-list

• 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

Tasks

• Create a Sort Class

o Member variables

◦ dynamic array of ints

◦ size of

◦ linked list head

◦ vector<int>

◦ random seed value

o Constructor(array size) o Destructor

o Overloaded << operator

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

• for testing

• To display your array.

• (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.

Grade Sheet – 125 points

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

Insertion Sort Linked List

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)

1. assume head points to the head of an unsorted linked list

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

a. unlink the front node of unsorted linked list (current node is this newly unlinked node)

i. when done, head points to the node after current node

b. find the proper place to insert current node into the temp list

i. if temp list is currently empty, add current node to the front of temp list

ii. else if current node’s value is less or equal to temp list’s value, add current node to beginning of temp list

iii. else go through the rest of the temp list and insert current element before the next element which has a value greater or equal to current element

4. update head pointer with the temp list pointer