Sorting and Searching Project Problem Statement for Sorting and Searching Project Design a program that will take an unsorted list of names and use the Insertion Sort algorithm to sort them. The program then asks the user to enter names to see if they are on the list. The program will use the recursive Binary Search algorithm to see if the name is in the list. The search should be enclosed in a loop so that the user can ask for names until they enter the sentinel value 'quit' Design Considerations The main program will provide an unsorted list of names. The list will be sorted using the Insertion Sort algorithm. Once the list is sorted, the user will provide names to search for in the list. The search will be conducted using the Recursive Binary Search Algorithm. A message will be printed displaying whetherthe name was found or not found on the list. This last part will be done inside a loop where the user will enter 'quit' when they are done searching for names. The algorithm for the main()isshown below. This is notin pseudocode, it is left up to the student to convert this algorithm into a Python function: main() Initialize the unsorted list of names Print the unsorted list Sort the list using the Insertion Sort algorithm Print the sorted list Get a name from the user While the name is not equal to 'quit' Search for the name in the sorted list using the Recursive Binary Search algorithmif the name is found Write name, " was found" else Write name, "was not found" Get a name from the user The Insertion Sort and Recursive Binary Search are to be written as separate functions (see below). Use this unsorted list of names for testing: ['Paul', 'Aaron', 'Jacob', 'James','Bill', 'Sara', 'Cathy', 'Barbara', 'Amy', 'Jill'] Part 1. Insertion Sort Here is the pseudocode for the Insertion Sort function insertionSort(data) Set current to 1 length = len(data) WHILE (current < length) Set index to current Set placeFound to FALSE WHILE (index > 0 AND NOT placeFound) IF (data[index] last) RETURN FALSE ELSE Set middle to (first + last) // 2 IF (item equals data[middle]) RETURN TRUE ELSE IF (item < data[middle]) RETURN BinarySearch(data, first, middle–1, item) ELSE RETURN BinarySearch(data, middle+1, last, item)
Sorting and Searching Project
Problem Statement for Sorting and Searching Project
Design a program that will take an unsorted list of names and use the Insertion Sort
Design Considerations
The main program will provide an unsorted list of names. The list will be sorted using the Insertion Sort algorithm. Once the list is sorted, the user will provide names to search for in the list. The search will be conducted using the Recursive Binary Search Algorithm. A message will be printed displaying whetherthe name was found or not found on the list. This last part will be done inside a loop where the user will enter 'quit' when they are done searching for names.
The algorithm for the main()isshown below. This is notin pseudocode, it is left up to the student to convert this algorithm into a Python function:
main()
Initialize the unsorted list of names
Print the unsorted list
Sort the list using the Insertion Sort algorithm
Print the sorted list
Get a name from the user
While the name is not equal to 'quit'
Search for the name in the sorted list using the Recursive Binary Search algorithmif the name is found
Write name, " was found"
else
Write name, "was not found"
Get a name from the user
The Insertion Sort and Recursive Binary Search are to be written as separate functions (see below).
Use this unsorted list of names for testing:
['Paul', 'Aaron', 'Jacob', 'James','Bill', 'Sara', 'Cathy', 'Barbara', 'Amy', 'Jill']
Part 1. Insertion Sort
Here is the pseudocode for the Insertion Sort function
insertionSort(data)
Set current to 1
length = len(data)
WHILE (current < length)
Set index to current
Set placeFound to FALSE
WHILE (index > 0 AND NOT placeFound)
IF (data[index] <data[index –1])
Swap(data, index, index –1])
Set index to index –1
ELSE
Set placeFound to TRUE
Set current to current + 1
This algorithm has an abstract step:
Swap(data, index1, index2)
Set tempItem to data[index1]
Set data[index1] to data[index2]
Set data[index2] totempItem
Part 2. Binary Search
Write the code to implement the Recursive Binary Search algorithm as a function. Here is the pseudocode for that function:
BinarySearch(data,first, last, item)
IF (first > last)
RETURN FALSE
ELSE
Set middle to (first + last) // 2
IF (item equals data[middle])
RETURN TRUE
ELSE
IF (item < data[middle])
RETURN BinarySearch(data, first, middle–1, item)
ELSE
RETURN BinarySearch(data, middle+1, last, item)
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 4 images
