I have done the first part a. Only need an answer for part B. Programming language C++.

Part a.

Write a program that solves a word search puzzle. The program reads an n x n grid of letters from a file and prints out all the words that can be found in the grid. Words can be found in the array by starting from any letter and reading left, right, up, down, or along any of the four diagonals. Words can also wrap around the edges of the array. Words must be at least 5 characters long. The list of k possible words is included in the file dictionary. Several sample word search puzzles are also provided. The goal is to find an algorithm that solves this problem that runs as quickly as possible for large n and k. Part a 1. Implement a class called dictionary that reads the words from the dictionary file and stores them in a vector, and which includes: (a) a function to read the words from the dictionary file, (b) an overloaded output operator to print the word list, (c) functions that sort the words using selectionsort, (d) a function to handle word lookups using binary search. 2. Implement a class called grid that reads the letters in the grid from a file and stores them in a matrix. 3. Implement a global function findMatches() that is passed the dictionary and the grid as parameters and which prints out all words that can be found in the grid. 4. Implement a global function search() which reads the name of the grid file from the keyboard and prints out all words from the word list that can be found in the grid.

Part b.

In this part, solve the word search puzzle by using the quicksort algorithm and the heapsort algorithm to sort the words in the dictionary.

1. Implement a member function of dictionary that sorts the words using quicksort

2. Implement the template class heap that stores objects in a heap of type vector, and which includes: (a) functions parent(int), left(int), right(int), and getItem(int n) which returns the nth item in the heap, (b) for a max-heap, functions initializeMaxHeap(), maxHeapify(), and buildMaxHeap(), (c) function heapsort().

3. Implement a member function of dictionary that sorts the words using heapsort. Since the heap is only used to sort the word list, you can declare the heap within the dictionary::heapsort function, copy the unsorted words into the heap, sort the words, and then copy the words out. Then the dictionary::binarySearch function can be used to look up words.

4. Modify the global function search(int) which reads the name of the grid file from the keyboard and prints out all words from the word list that can be found in the grid. The integer parameter is used to select the sorting algorithm used.