HW4

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 2^nd 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.

Speedup_i = SFlaoswteerr SSAA eexxeecc ttiimmee

SA: Sorting Algorithm

The same formula applies when comparing between AVL tree, BST and the vector search times:

Speedup_i = 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 dont 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