Design, write, and execute a C++ program that will demonstrate the use of severa

Question

Design, write, and execute a C++ program that will demonstrate the use of several sort and search routines by allowing the user to work with an ongoing, "current" list by repeatedly choosing actions from the following menu: 1. Reset the current list from the keyboard 2. Reset the current list using randomly generated elements 3. Perform Bubble Sort on the current list 4. Perform Insertion Sort on the current list 5. Perform Selection Sort on the current list 6. Perform Linear Search on the current list 7. Perform Binary Search on the current list 8. Quit the program Here are some requirements for your program: Your program should be able to handle lists with up to 50 items. When your program starts executing, it should automatically start with a current list of 0 items; in other words, the current list should start off as an empty list. Your program should track the fact that this empty current list is known to be ordered. Before displaying the menu each time, the program should display the current list. If the current list is empty, then the phrase "(empty)" should be displayed. The current order status (known or not known to be ordered) should also be displayed. Whenever the user chooses to reset the current list from the keyboard, the user should then be allowed to enter in between 0 and 50 positive elements from the keyboard, signaling the end of the input by entering the "sentinel" element of -1. Whenever the user chooses to reset the current list using randomly generated elements, the user should be asked for the size of the list (a value between 0 and 50), as well as the lowest lower and upper limits that the elements in the list could have (the "range" of the elements), and then the program should automatically generate list elements within the given range using the random number generator. Whenever the user chooses to reset the current list (whether by keyboard or by randomly generated elements), the program should track the fact that this new current list is not known to be ordered. Whenever the user chooses to perform a sort on the current list, the program should perform the chosen sort, and in doing so also count the actual number of element comparisons and element movements used by the sort, and then print out a short report showing both the theoretical number of element comparisons and element movements necessary for sorting a list of this size, as well as the counted number of element comparisons and element movements that were actually used to sort the current list. The program should also track the fact that this re-arranged current list is now known to be ordered. Whenever the user chooses to perform a search on the current list, the program should first ask the user for a target element to search for, then perform the search, and in doing so also count the actual number of element comparisons used by the search, then print out the results of the search (whether or not the target was found, and if it was, what position it was found in), and then finally print out a short report showing the theoretical number of element comparisons necessary for searching a list of this size, as well as the counted number of element comparisons that were actually used to search the current list. Whenever the user chooses to perform a Binary Search on the current list, the program should first check to see if the current list is known to be ordered. If it is, then the program should continue with the Binary Search. If it is not, then the program should remind the user to first sort the list before attempting a Binary Search, and then decline to perform the Binary Search at this time. All inputs given by the user to your program should undergo data validation to insure that they are correct in data type and range before being used. You should write this program by extending the AList class that we are currently developing in our CS215 lecture. At a minimum, your program must include and use the following C++ methods and associated parameters: AList::Read: fills up the native object list with positive data given by the user from the keyboard, until the sentinel -1 is entered AList::GenerateRandomList: given the desired number of elements to be on the list, and given the desired lower and upper range values for these elements, fills up the native object list with that many randomly generated elements within the given range AList::Print: displays the native object list's elements on the monitor AList::BubbleSort: sorts the native object list using Bubble Sort, and sends back the number of list element comparisons and the number of list element movements used AList::InsertionSort: sorts the native object list using Insertion Sort, and sends back the number of list element comparisons and the number of list element movements used AList::SelectionSort: sorts the native object list using Selection Sort, and sends back the number of list element comparisons and the number of list element movements used AList::LinearSearch: given a target item to search for, searches the native object list using Linear Search, and sends back whether or not that item was found, and if so, at what list position, as well as the number of list element comparisons used AList::BinarySearch: given a target item to search for, and given a native object list that is already sorted, searches the native object list using Binary Search, and sends back whether or not that item was found, and if so, at what list position it was found, as well as the number of list element comparisons used In order to make your main function relatively modular and easy to read, you should also include additional methods and/or functions as necessary. Here are some hints to make your coding easier: Code and test each of the five fundamental sort and search methods separately. When they are working properly, then you can combine them into the overall program. There are some C++ library function that you can use to help you generate random numbers. To initialize the random number system (by initializing the so-called random number seed) use srand(int(time(0))). This statement should be executed exactly once (no more) for each complete execution of your program, and before your program attempts to generate any actual random numbers. To generate exactly one random number, use number = rand(), where number is some local variable of your own that you are using to "ctach" the functional value of rand(). To have access to the srand, rand, and time library functions, you should #include both the stdlib.h and the time.h libraries at the top of your program. When generating random numbers to fill up the current list, the modulus operator (%) will be of great help to keep them within the desired range. Also, don't worry if you don't generate every possible element within that range -- missing or duplicate randomly generated elements are normal.

Explanation / Answer

Sort and Search Demo Program, version 1.0 (c) 2002, (your name) Current list: (empty) (KNOWN to be ordered) Actions: 1. Reset the current list from the keyboard 2. Reset the current list using randomly generated elements 3. Perform Bubble Sort on the current list 4. Perform Insertion Sort on the current list 5. Perform Selection Sort on the current list 6. Perform Linear Search on the current list 7. Perform Binary Search on the current list 8. Quit the program Choose an action: 2 Resetting the current list using randomly generated elements. Enter the desired number of elements (0 to 50): maybe Response must be a whole number, try again: 51 Response must be between 0 and 50, try again: 5 Enter the lower limit of the range: 10 Enter the upper limit of the range: 30 Finished resetting, 5 elements between 10 and 30 randomly generated. Current list: 15 22 11 26 17 (NOT KNOWN to be ordered) Actions: 1. Reset the current list from the keyboard 2. Reset the current list using randomly generated elements 3. Perform Bubble Sort on the current list 4. Perform Insertion Sort on the current list 5. Perform Selection Sort on the current list 6. Perform Linear Search on the current list 7. Perform Binary Search on the current list 8. Quit the program Choose an action: 7 Sorry, since the current list is not known to be ordered, the Binary Search cannot be performed at this time. Please sort the current list first. Current list: 15 22 11 26 17 (NOT KNOWN to be ordered) Actions: 1. Reset the current list from the keyboard 2. Reset the current list using randomly generated elements 3. Perform Bubble Sort on the current list 4. Perform Insertion Sort on the current list 5. Perform Selection Sort on the current list 6. Perform Linear Search on the current list 7. Perform Binary Search on the current list 8. Quit the program Choose an action: 8 Quitting Sort and Search Demo Program, version 1.0

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.