$25
CS300-Homework 5 Sorting Solved
In this homework, you have a PhoneBook that you kept updating without caring about sorting it alphabetically, and since you are a CS student, you care about the time taken to sort the PhoneBook so you want the fastest algorithm to perform this operation and the fastest search structure. Therefore, you must compare 4 Sorting algorithms and conclude which one is faster then perform search operation as you did in HW2.
You will be implementing the PhoneBook as you did already in the 2nd homework, in addition to using vectors to store the list of contacts in it loaded from the input file. You should load the PhoneBook in 4 different vectors then perform comparison between them (in terms of running times).
The sorting algorithms:
● Insertion Sort
● Quick Sort (pivot = [median])
● Merge Sort (in place; without using auxiliary memory storage) ● Heap Sort
Please note that after sorting the vectors, you should conduct a binary search about a contact or list of contacts on the sorted vector and compare the running times with those of the BST and AVL tree.
Program Flow
First, you have to read the input file and load the PhoneBook into vectors where you are going to apply a sorting algorithm on each one. In order to insert a contact, you need to insert its information into a data structure of your definition. There are 2 types of search that should be valid in your implementation, Partial and Full name search (similar to HW2).
After loading the PhoneBook into each vector copy, your program should ask for a search query (Partial or Full), then all 4 vectors should be sorted according to the sorting algorithms listed above.
Concerning the search operation, it should be performed on each PhoneBook copy (BST, AVL tree and sorted vector) so we can make comparisons between the search running times on each data structure.
For the comparisons, you should measure the running time without printing anything to the screen then display it for each structure.
You are also required to calculate the speedups between algorithms, the equation for calculating the speedup is given below.
Speedupi = SFlaoswteerr SSAA eexxeecc ttiimmee
SA: Sorting Algorithm
The same formula applies when comparing between AVL tree, BST and the vector search times:
Speedupi = SFlaoswteerr SSeeaarrcchh eexxeecc ttiimmee
Input
First, your program should ask for an input file (PhoneBook file) then it asks for a query entry where you should enter a full/partial contact name in one line.
Output
After inserting the inputs, you should first display the sorting times, second, the search times for AVL, BST and the vector, and last, the speedups list (check the sample runs to have a more clear image).
After getting the execution times, you will be able to compute the speedups and also display them.
Important notes
➔ Even though you are not asked to print out the results to the screen, your search functions should return correct results, this will be tested during the grading process.
➔ Your classes should be template-based .
➔ Note: The previous sample runs were taken from a machine with the following specifications:
● CPU: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz (4 cores - 8 threads) ● RAM: 4GiB
Therefore, we understand that you have different machines, it can be powerful or weak in terms of specifications, so, we don’t expect the speedup ratios to be exactly the same as in the sample runs, however, the results should be reasonable and conform with the results correctness, for example:
● In sample run 6, the speedup ratio (Insertion Sort / Quick Sort) is so high (119.058) so we will accept lower ratios like 30 or 20 or even 10. However, ratios beneath 5 would be suspicious and ratios like 0.9 or less (less than 1) are not acceptable and it shows that the code is problematic somehow.
Sample runs
Sample Run 1
Please enter the contact file name:
PhoneBook-sample2.txt Please enter the word to be queried :
Shane
Sorting the vector copies
======================================
Quick Sort Time: 267392 Nanoseconds
Insertion Sort Time: 1485445 Nanoseconds
Merge Sort Time: 1375031 Nanoseconds
Heap Sort Time: 518291 Nanoseconds
Searching for Shane
======================================
The search in BST took 20098 Nanoseconds
The search in AVL took 9647 Nanoseconds
Binary Search Time: 16210 Nanoseconds
SpeedUps in search
======================================
(BST / AVL) SpeedUp = 2.08334
(Binary Search / AVL) SpeedUp = 1.68032
(Binary Search / BST) SpeedUp = 0.806548
SpeedUps between Sorting Algorithms
======================================
(Insertion Sort/ Quick Sort) SpeedUp = 5.55531
(Merge Sort / Quick Sort) SpeedUp = 5.14238
(Heap Sort / Quick Sort) SpeedUp = 1.93832
Sample Run 2
Char
Sorting the vector copies
======================================
Quick Sort Time: 26376 Nanoseconds
Insertion Sort Time: 44829 Nanoseconds
Merge Sort Time: 42555 Nanoseconds
Heap Sort Time: 41510 Nanoseconds
Searching for Char
====================
The search in BST took 4635 Nanoseconds
The search in AVL took 5161 Nanoseconds
Binary Search Time: 10613 Nanoseconds
SpeedUps in search
======================================
(BST / AVL) SpeedUp = 0.898082
(Binary Search / AVL) SpeedUp = 2.05638
(Binary Search / BST) SpeedUp = 2.28975
SpeedUps between Sorting Algorithms
======================================
(Insertion Sort/ Quick Sort) SpeedUp = 1.69961
(Merge Sort / Quick Sort) SpeedUp = 1.6134
(Heap Sort / Quick Sort) SpeedUp = 1.57378
Sample Run 3
Tina Gulko
Sorting the vector copies
======================================
Quick Sort Time: 93656 Nanoseconds
Insertion Sort Time: 512859 Nanoseconds
Merge Sort Time: 489748 Nanoseconds
Heap Sort Time: 202962 Nanoseconds
Searching for Tina
====================
The search in BST took 1260 Nanoseconds
The search in AVL took 1193 Nanoseconds
Binary Search Time: 3889 Nanoseconds
SpeedUps in search
======================================
(BST / AVL) SpeedUp = 1.05616
(Binary Search / AVL) SpeedUp = 3.25985
(Binary Search / BST) SpeedUp = 3.08651
SpeedUps between Sorting Algorithms
======================================
(Insertion Sort/ Quick Sort) SpeedUp = 5.47599
(Merge Sort / Quick Sort) SpeedUp = 5.22922
(Heap Sort / Quick Sort) SpeedUp = 2.1671
Sample Run 4
Gulsen Demiroz
Sorting the vector copies
======================================
Quick Sort Time: 135189 Nano secs
Insertion Sort Time: 435134 Nano secs
Merge Sort Time: 449873 Nano secs
Heap Sort Time: 235754 Nano secs
Searching for Gulsen
====================
The search in BST took 2665 Nanoseconds
The search in AVL took 2730 Nanoseconds
Binary Search Time: 9550 Nanoseconds
SpeedUps in search
======================================
(BST / AVL) SpeedUp = 0.97619
(Binary Search / AVL) SpeedUp = 3.49817
(Binary Search / BST) SpeedUp = 3.58349
SpeedUps between Sorting Algorithms
======================================
(Insertion Sort/ Quick Sort) SpeedUp = 3.21871
(Merge Sort / Quick Sort) SpeedUp = 3.32773
(Heap Sort / Quick Sort) SpeedUp = 1.74388
Sample Run 5
PhoneBook-shuffled.txt Please enter the word to be queried :
Virg
Sorting the vector copies
======================================
Quick Sort Time: 10056248 Nanoseconds
Insertion Sort Time: 1186275960 Nanoseconds
Merge Sort Time: 981504897 Nanoseconds
Heap Sort Time: 18064775 Nanoseconds
Searching for Virg
======================================
The search in BST took 26106 Nanoseconds
The search in AVL took 7118 Nanoseconds
Binary Search Time: 8562 Nanoseconds
SpeedUps in search
======================================
(BST / AVL) SpeedUp = 3.6676
(Binary Search / AVL) SpeedUp = 1.20287
(Binary Search / BST) SpeedUp = 0.327971
SpeedUps between Sorting Algorithms
======================================
(Insertion Sort/ Quick Sort) SpeedUp = 117.964
(Merge Sort / Quick Sort) SpeedUp = 97.6015
(Heap Sort / Quick Sort) SpeedUp = 1.79637
Sample run 6
PhoneBook-shuffled.txt Please enter the word to be queried :
James
Sorting the vector copies
======================================
Quick Sort Time: 9994504 Nanoseconds
Insertion Sort Time: 1189930420 Nanoseconds
Merge Sort Time: 983665907 Nanosecond
Heap Sort Time: 17199362 Nanoseconds
Searching for James
======================================
The search in BST took 132991 Nanoseconds
The search in AVL took 38027 Nanoseconds
Binary Search Time: 10237 Nanoseconds
SpeedUps in search
======================================
(BST / AVL) SpeedUp = 3.49728
(Binary Search / AVL) SpeedUp = 0.269203
(Binary Search / BST) SpeedUp = 0.0769751
SpeedUps between Sorting Algorithms
======================================
(Insertion Sort/ Quick Sort) SpeedUp = 119.058
(Merge Sort / Quick Sort) SpeedUp = 98.4207
(Heap Sort / Quick Sort) SpeedUp = 1.72088
