Problem Set 4: Sorting, Searching and Hashing
Problem 1(a) and 2(a) of this assignment requires a C++ compiler. As usual, you must submit the actual source
code files (ending in .cpp) so that I can compile and run your programs, and you programs must compile. The
remaining problems must be written up in a Microsoft Word document. Remember to include your name and
course number within all of the files and documents that you submit.
1. [5 points] Sorting
Read the assigned chapter and the notes for Week 7 located in the Course Documents area, and then do the
(a) [3 points] Modify the HeapSort.cpp file to implement the required functions for a heap sort algorithm.
Once the functions have been implemented, the program will sort and print list of strings in alphabetical
order. The heapSort() function will call the buildHeap() and heapify() functions. The buildHeap()
function will also call the heapify() function. Your program must use these functions.
Hint: You only need to provide the necessary details for these three functions, which will be similar to
those in your book, but they will not use templates or the class as described in the book. Thus, in the
textbook, the first line with the template prototype is not in the implementation. You must also replace
elemType within the functions in the book implementations with the keyword string. Also, notice that
the list variable itself is passed in as the first parameter within each of these functions. The
printItems() and main() function will not need to change.
(b) [1.5 points] Explain the differences on how the Quick Sort algorithm and the Merge Sort algorithm
handle partitioning the list to be sorted.
2. [5 points] Searching and Hashing
Read the assigned chapter and notes for Week 8 located in the Course Documents area, and then do the following
(a) [3 points] Modify the BinarySearch.cpp file to implement the required function for a binary search
algorithm. Once the function has been implemented, the program returns the index location of the item in
the array if it is found; otherwise a -1 will be returned. Remember that arrays in C++ are zero-based, so
the first position has an index of 0.
Hint: Again, you only need to provide the necessary details for the binarySearch() function, which will
be similar to the one in your book, but it will not use templates or the class as described in the book.
Again, in the textbook, the first line with the template prototype is not necessary in our implementation.
Unlike the textbook, our function will take in three variables: list, length, and item. The function will
return the position of the string within the array, or -1 if the item is not found. The function main() will
not need to change
|$35.00||no category||fornicola||1 time(s)|