Sorting Algorithms Solution

$30.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

• 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


error: Content is protected !!