CS300 - Homework #4 – Sorting and Searching - Solved

In this homework, you are given an unsorted PhoneBook and asked to sort it in alphabetical order. Since you are a CS student, you care about the time taken to sort the PhoneBook so you want the fastest comparison-based sorting algorithm to perform this operation. Therefore, you must compare the given 4 Sorting algorithms and conclude which one is faster. Also, since fundamental usage of a PhoneBook is search for some names, you are expected to implement 2 search algorithms to compare.

The sorting algorithms you will compare are:

●     Insertion Sort

●     Quick Sort      (pivot=median) (use Insertion Sort when size < 10)

●     Merge Sort     (in place; without using auxiliary memory storage) ● Heap Sort

The searching algorithms you will compare are:

●     Sequential Search ●  Binary Search

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. Here is a detailed simple input txt example.

PhoneBook.txt

 

As is shown in the sample PhoneBook.txt file, every line is for one person and Name, Surname,

Telephone, and City are the provided information. You do not have any assumption on the length of the name and surname which are separated by a space. The telephone has a standard length of 13 characters. You also do not have any assumption on the length of the city name, but it is one word for sure.

Another input you will ask is a search query. There are two types of searches you need to observe over the dataset, which is partial and full name search:

●     Full Contact Name Search

In this case, the user provides the whole name and surname and you will be searching for an exact match in both.

●     Partial Contact Name Search

In this case, your input is part of the name starting from the beginning and you do not have pre-knowledge of where it ends. In the case of repeated partial names and key matches, you need to detect every match and print them out.

Output
After you receive the inputs (dataset and search query), you should first display the sorting times in Nanoseconds and then the speedups of the sorting algorithms. Afterward, the search times need to be printed, and last, the speedup list for search algorithms (check the sample runs to have a clearer image). After getting the execution times, you will be able to compute the speedups and display them. Additionally, you are expected to print the search results (see sample runs).

Program Flow
After taking the inputs, Firstly, you have to read the input file and load the PhoneBook into different vectors where you are going to apply a sorting algorithm on each one. There are 2 types of search that should be valid in your implementation, Partial and Full name search. They are described in the previous part of this document.

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 the same sorted PhoneBook copy so you can make comparisons between the search running times on both algorithms.

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:

The same formula applies when comparing between the𝑆𝑝𝑒𝑒𝑑𝑢𝑝 = 𝑆𝑙𝑜𝑤𝑒𝑟𝐹𝑎𝑠𝑡𝑒𝑟  𝑆𝑜𝑟𝑡𝑖𝑛𝑔𝑆𝑜𝑟𝑡𝑖𝑛𝑔  𝐴𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚𝐴𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚vector search times:  𝑒𝑥𝑒𝑐𝑒𝑥𝑒𝑐  𝑡𝑖𝑚𝑒𝑡𝑖𝑚𝑒 𝑆𝑝𝑒𝑒𝑑𝑢𝑝 = 𝑆𝑙𝑜𝑤𝑒𝑟𝐹𝑎𝑠𝑡𝑒𝑟  𝑆𝑒𝑎𝑟𝑐ℎ𝑆𝑒𝑎𝑟𝑐ℎ  𝑒𝑥𝑒𝑐𝑒𝑥𝑒𝑐  𝑡𝑖𝑚𝑒𝑡𝑖𝑚𝑒 

Important notes
➔   You are asked to print out the search results to the screen, your search functions should return correct results, this will be tested during the grading process.

➔   In Quick Sort Algorithm, you are expected to choose the pivot as the median.

➔   In Merge Sort, you are expected to have an in-place version. Means no extra memory usage.

➔   Your classes should be template-based.

➔   Note: The provided sample runs were taken from a machine with the following specifications:

●     CPU: Intel(R) Core(TM) i5-7300HQ CPU @ 2.50GHz

●     RAM: 16GB

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 correctness of the results, for example:

●     In sample run 4, the speedup ratio (Insertion Sort / Quick Sort) is so high (31.779) so we will accept lower ratios like 30 or 20 or even 10. However, ratios beneath 2 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.

➔   In order to find the exact time, you can run the search function N times then you take the measured time and divide it by N, you will have much sharper timings.

Example:

int N = 1000; // if it takes too much time then N = 100 int timeStart // start measuring for (int i = 0; i < N; i++) search_function()

int timeEnd // end measuring executionTime = (endTime - startTime) / N


Sample runs
Sample Run 1
Please enter the contact file name:

PhoneBook-sample1.txt Please enter the word to be queried :

Mario

Sorting the vector copies

======================================

Quick Sort Time: 309111 Nanoseconds

Insertion Sort Time: 219424 Nanoseconds

Merge Sort Time: 259642 Nanoseconds

Heap Sort Time: 409247 Nanoseconds

Searching for Mario

====================================== Search results for Binary Search:

MARIO does NOT exist in the dataset

Binary Search Time: 51550 Nanoseconds

Search results for Sequential Search:

MARIO does NOT exist in the dataset

Sequential Search Time: 165588 Nanoseconds

SpeedUp between Search Algorithms

======================================

(Sequential Search/ Binary Search) SpeedUp = 3.21218

SpeedUps between Sorting Algorithms

======================================

(Insertion Sort/ Quick Sort) SpeedUp = 0.709855

(Merge Sort / Quick Sort) SpeedUp = 0.839964

(Heap Sort / Quick Sort) SpeedUp = 1.32395

Sample run 2
Please enter the filename:

PhoneBook-sample2.txt Please enter the word to be queried :

Robert

Sorting the vector copies

======================================

Quick Sort Time: 4686352 Nanoseconds

Insertion Sort Time: 15465172 Nanoseconds

Merge Sort Time: 15308845 Nanoseconds

Heap Sort Time: 8123151 Nanoseconds

Searching for Robert

====================================== Search results for Binary Search:

ROBERT CAMACHO +905556997035 Istanbul

ROBERT COY +905559274775 Bursa

ROBERT DELGENIO +905535624463 Bursa

ROBERT FISCHER +905536567181 Istanbul

ROBERT KINCHEN +905585715179 Ankara

ROBERT MCMILLIN +905566459683 Mugla

ROBERT MOSS +905596290308 Mugla

ROBERTA CARLYON +905592886254 Mugla

Binary Search Time: 109381 Nanoseconds

Search results for Sequential Search:

ROBERT CAMACHO +905556997035 Istanbul

ROBERT COY +905559274775 Bursa

ROBERT DELGENIO +905535624463 Bursa

ROBERT FISCHER +905536567181 Istanbul

ROBERT KINCHEN +905585715179 Ankara

ROBERT MCMILLIN +905566459683 Mugla

ROBERT MOSS +905596290308 Mugla

ROBERTA CARLYON +905592886254 Mugla

Sequential Search Time: 1765180 Nanoseconds SpeedUp between Search Algorithms

======================================

(Sequential Search/ Binary Search) SpeedUp = 16.1379

SpeedUps between Sorting Algorithms

======================================

(Insertion Sort/ Quick Sort) SpeedUp = 3.30005

(Merge Sort / Quick Sort) SpeedUp = 3.26669

(Heap Sort / Quick Sort) SpeedUp = 1.73336


Sample Run 3
Please enter the filename:

PhoneBook-sample3.txt Please enter the word to be queried :

Tina Gulko

Sorting the vector copies

======================================

Quick Sort Time: 2499417 Nanoseconds

Insertion Sort Time: 4530183 Nanoseconds

Merge Sort Time: 4998825 Nanoseconds

Heap Sort Time: 3905338 Nanoseconds

Searching for Tina Gulko

====================================== Search results for Binary Search:

TINA GULKO +905555214353 Izmir

Binary Search Time: 156526 Nanoseconds

Search results for Sequential Search:

TINA GULKO +905555214353 Izmir

Sequential Search Time: 937277 Nanoseconds

SpeedUp between Search Algorithms

======================================

(Sequential Search/ Binary Search) SpeedUp = 5.988

SpeedUps between Sorting Algorithms

======================================

(Insertion Sort/ Quick Sort) SpeedUp = 1.8125

(Merge Sort / Quick Sort) SpeedUp = 2

(Heap Sort / Quick Sort) SpeedUp = 1.5625

Sample Run 4
Please enter the filename:

PhoneBook-shuffled.txt Please enter the word to be queried :

Gulsen Demiroz

Sorting the vector copies

======================================

Quick Sort Time: 101234080 Nanoseconds

Insertion Sort Time: 3217155950 Nanoseconds

Merge Sort Time: 2795505390 Nanoseconds

Heap Sort Time: 214487870 Nanoseconds

Searching for Gulsen Demiroz

====================================== Search results for Binary Search:

GULSEN DEMIROZ does NOT exist in the dataset

Binary Search Time: 312429 Nanoseconds

Search results for Sequential Search:

GULSEN DEMIROZ does NOT exist in the dataset

Sequential Search Time: 26556300 Nanoseconds

SpeedUp between Search Algorithms

======================================

(Sequential Search/ Binary Search) SpeedUp = 84.9994

SpeedUps between Sorting Algorithms

======================================

(Insertion Sort/ Quick Sort) SpeedUp = 31.7794

(Merge Sort / Quick Sort) SpeedUp = 27.6143

(Heap Sort / Quick Sort) SpeedUp = 2.11873

Sample Run 5
Please enter the filename:

PhoneBook-shuffled.txt Please enter the word to be queried :

William

Sorting the vector copies

======================================

Quick Sort Time: 103670750 Nanoseconds

Insertion Sort Time: 3013754750 Nanoseconds

Merge Sort Time: 2668554670 Nanoseconds

Heap Sort Time: 195263440 Nanoseconds

Searching for William

====================================== Search results for Binary Search:

WILLIAM AMMANN +905511932805 Bursa

WILLIAM ARTHUR +905562451286 Mugla

WILLIAM BAIG +905550568328 Izmir

WILLIAM BASH +905586488892 Izmir

WILLIAM BOOTHBY +905589026291 Mugla

WILLIAM BYRD +905524927636 Ankara

WILLIAM CHILDS +905533803958 Ankara

WILLIAM CHOQUETTE +905594109713 Izmir

WILLIAM CLINE +905585739452 Ankara

WILLIAM CONSTANT +905526153465 Ankara

WILLIAM CORONADO +905527551169 Istanbul

WILLIAM COULSON +905547697706 Ankara

WILLIAM CRAWFORD +905588504000 Istanbul

WILLIAM DILLON +905560055969 Izmir

WILLIAM EVANS +905516331172 Ankara

WILLIAM FELLHOELTER +905582753443 Izmir

WILLIAM FRANKLIN +905556802033 Mugla

WILLIAM FULTS +905541092648 Istanbul

WILLIAM GARCIA +905518961107 Istanbul

WILLIAM GRAY +905538931487 Bursa

WILLIAM GREEN +905525236487 Mugla

WILLIAM GRIMES +905536548349 Izmir

WILLIAM HARRISON +905586333675 Istanbul WILLIAM HAYES +905551962201 Istanbul

WILLIAM HERNANDEZ +905553079127 Istanbul

WILLIAM HINTZE +905549889332 Izmir

WILLIAM HOLDER +905512104631 Bursa

WILLIAM HOLLEMAN +905514849636 Mugla

WILLIAM HOLLOBAUGH +905524353742 Ankara

WILLIAM HULL +905556815354 Ankara

WILLIAM HUMPHREYS +905579083699 Ankara

WILLIAM ISLAS +905550159250 Bursa

WILLIAM JIMENEZ +905576076829 Izmir

WILLIAM JOHNSON +905546114538 Istanbul

WILLIAM KELLY +905554525839 Izmir

WILLIAM KOCI +905577674896 Izmir

WILLIAM LEWIS +9055419074294 Ankara

Binary Search Time: 156207 Nanoseconds

Search results for Sequential Search:

WILLIAM AMMANN +905511932805 Bursa

WILLIAM ARTHUR +905562451286 Mugla

WILLIAM BAIG +905550568328 Izmir

WILLIAM BASH +905586488892 Izmir

WILLIAM BOOTHBY +905589026291 Mugla

WILLIAM BYRD +905524927636 Ankara

WILLIAM CHILDS +905533803958 Ankara

WILLIAM CHOQUETTE +905594109713 Izmir

WILLIAM CLINE +905585739452 Ankara

WILLIAM CONSTANT +905526153465 Ankara

WILLIAM CORONADO +905527551169 Istanbul

WILLIAM COULSON +905547697706 Ankara

WILLIAM CRAWFORD +905588504000 Istanbul

WILLIAM DILLON +905560055969 Izmir

WILLIAM EVANS +905516331172 Ankara

WILLIAM FELLHOELTER +905582753443 Izmir

WILLIAM FRANKLIN +905556802033 Mugla

WILLIAM FULTS +905541092648 Istanbul

WILLIAM GARCIA +905518961107 Istanbul

WILLIAM GRAY +905538931487 Bursa

WILLIAM GREEN +905525236487 Mugla

WILLIAM GRIMES +905536548349 Izmir WILLIAM HARRISON +905586333675 Istanbul

WILLIAM HAYES +905551962201 Istanbul

WILLIAM HERNANDEZ +905553079127 Istanbul

WILLIAM HINTZE +905549889332 Izmir

WILLIAM HOLDER +905512104631 Bursa

WILLIAM HOLLEMAN +905514849636 Mugla

WILLIAM HOLLOBAUGH +905524353742 Ankara

WILLIAM HULL +905556815354 Ankara

WILLIAM HUMPHREYS +905579083699 Ankara

WILLIAM ISLAS +905550159250 Bursa

WILLIAM JIMENEZ +905576076829 Izmir

WILLIAM JOHNSON +905546114538 Istanbul

WILLIAM KELLY +905554525839 Izmir

WILLIAM KOCI +905577674896 Izmir

WILLIAM LEWIS +9055419074294 Ankara

Sequential Search Time: 26470800 Nanoseconds

SpeedUp between Search Algorithms

======================================

(Sequential Search/ Binary Search) SpeedUp = 169.46

SpeedUps between Sorting Algorithms

======================================

(Insertion Sort/ Quick Sort) SpeedUp = 29.0704

(Merge Sort / Quick Sort) SpeedUp = 25.7407

(Heap Sort / Quick Sort) SpeedUp = 1.8835

Sample Run 6
Please enter the filename:

PhoneBook-shuffled.txt Please enter the word to be queried :

Virg

Sorting the vector copies

======================================

Quick Sort Time: 103523720 Nanoseconds

Insertion Sort Time: 3200932540 Nanoseconds

Merge Sort Time: 2754943720 Nanoseconds

Heap Sort Time: 214178500 Nanoseconds

Searching for Virg

====================================== Search results for Binary Search:

VIRGIE DILORENZO +905522148183 Mugla

VIRGIL SCHIRO +905520736869 Ankara

VIRGINIA ATKINS +905599534420 Bursa

VIRGINIA BASQUEZ +905577945155 Istanbul

VIRGINIA BOWMAN +905554551074 Bursa

VIRGINIA BROWN +905575396124 Izmir

VIRGINIA BURNS +905575713316 Bursa

VIRGINIA HARTLE +905559017152 Istanbul

VIRGINIA HOBERG +905574933865 Izmir

VIRGINIA KAYSER +905588959312 Mugla

VIRGINIA MAJOR +905524248481 Bursa

VIRGINIA MEEKS +905559851680 Ankara

VIRGINIA OVERSTREET +905521897621 Bursa

VIRGINIA ROBINSON +905535242466 Ankara

VIRGINIA RUDDY +905559278674 Bursa

VIRGINIA SCHMITZ +905575344091 Mugla

VIRGINIA TESTER +905566236472 Bursa

VIRGINIA WOODHAMS +905543498083 Bursa

VIRGINIA ZAPATA +905591602872 Mugla

Binary Search Time: 156538 Nanoseconds Search results for Sequential Search:

VIRGIE DILORENZO +905522148183 Mugla

VIRGIL SCHIRO +905520736869 Ankara

VIRGINIA ATKINS +905599534420 Bursa

VIRGINIA BASQUEZ +905577945155 Istanbul

VIRGINIA BOWMAN +905554551074 Bursa

VIRGINIA BROWN +905575396124 Izmir

VIRGINIA BURNS +905575713316 Bursa

VIRGINIA HARTLE +905559017152 Istanbul

VIRGINIA HOBERG +905574933865 Izmir

VIRGINIA KAYSER +905588959312 Mugla

VIRGINIA MAJOR +905524248481 Bursa

VIRGINIA MEEKS +905559851680 Ankara

VIRGINIA OVERSTREET +905521897621 Bursa

VIRGINIA ROBINSON +905535242466 Ankara

VIRGINIA RUDDY +905559278674 Bursa

VIRGINIA SCHMITZ +905575344091 Mugla

VIRGINIA TESTER +905566236472 Bursa

VIRGINIA WOODHAMS +905543498083 Bursa

VIRGINIA ZAPATA +905591602872 Mugla

Sequential Search Time: 26269600 Nanoseconds

SpeedUp between Search Algorithms

======================================

(Sequential Search/ Binary Search) SpeedUp = 167.816

SpeedUps between Sorting Algorithms

======================================

(Insertion Sort/ Quick Sort) SpeedUp = 30.9198

(Merge Sort / Quick Sort) SpeedUp = 26.6117

(Heap Sort / Quick Sort) SpeedUp = 2.06888