Question

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'

Answer 1

See explaination for program code

Step-by-step explanation:

Code below:

def insertion_sort(names_list):

"""

function to sort name list using insertion sort

"""

for i in range(1, len(names_list)):

val = names_list[i]

temp = i

while temp > 0 and names_list[temp-1] > val:

names_list[temp] = names_list[temp-1]

temp = temp-1

names_list[temp] = val

def recursive_binary_search(names_list, left, right, search):

"""

function to search name in given list

"""

if right >= left:

# getting mid value

mid_index = int(left + (right - left)/2)

# comparing case insensitive name

if names_list[mid_index].lower() == search.lower():

# returning true if name found

return True

# shifting right left value as per comparing

elif names_list[mid_index].lower() > search.lower():

# calling function resursively

return recursive_binary_search(names_list, left, mid_index-1, search)

else:

return recursive_binary_search(names_list, mid_index+1, right, search)

else:

return False

def main():

# TODO: please feel free to add more name in below list

names = [

"Rakesh",

"Rahul",

"Amit",

"Gunjan",

"Alisha",

"Roy",

"Amrita"

]

print("sorting names....")

insertion_sort(names)

print("names sorted..")

while 1:

name = input("Enter name to search or quit to exit: ")

if name.lower() == 'quit':

break

# searhing name and based on result printing output

result = recursive_binary_search(names, 0, len(names)-1, name)

if result:

print("Name %s found in list" % name)

else:

print("Name %s not found in list" % name)

Answer 2

Check the explanation

Step-by-step explanation:

Program:

from modules import binSearch

from modules import insertionSort

unsort_list=['Paul', 'Aaron', 'Jacob', 'James', 'Bill', 'Sara', 'Cathy', 'Barbara', 'Amy', 'Jill']

print("The list of unsorted items are given below")

for i in unsort_list:

print(i)

insertionSort(unsort_list)

print("The list of sorted items are given below")

for i in unsort_list:

print(i)

while True:

userInput=raw_input("Enter the search string or quit to exit.. ")

if userInput == "quit":

print("quitting...")

break

else:

if binSearch(unsort_list, 0, len(unsort_list), userInput) != False:

print("%s was found." %userInput)

else:

print("%s was not found" %userInput)

USER> cat modules.py

def insertionSort(listarray):

"""This api in this module sorts the list in insertion sort algorithm"""

length=len(listarray)

currentIndex =1

while currentIndex < length:

index=currentIndex

placeFoundFlag=False

while index > 0 and placeFoundFlag == False:

if listarray[index] < listarray[index-1]:

temp=listarray[index-1]

listarray[index-1]=listarray[index]

listarray[index]=temp

index=index-1

else:

placeFoundFlag=True

currentIndex=currentIndex+1

def binSearch (listarray, init, lisLen, searchString):

"""This api in thie module search the given string from a given list"""

#check the starting position for the list array

if lisLen >= init:

#find the center point to start the search

mid = init + int((lisLen - init)/2)

#check if the string matches with the mid point index

if listarray[mid] == searchString:

return listarray[mid]

#now we will search recursively the left half of the array

elif listarray[mid] > searchString :

return binSearch(listarray, init, mid-1, searchString)

#now we will search recursively the right half of the array

else:

return binSearch(listarray, mid+1, lisLen, searchString)

else:

#string now found, return False

return False

Output:

The list of unsorted items are given below

Paul

Aaron

Jacob

James

Bill

Sara

Cathy

Barbara

Amy

Jill

The list of sorted items are given below

Aaron

Amy

Barbara

Bill

Cathy

Jacob

James

Jill

Paul

Sara

Enter the search string or quit to exit.. Amy

Amy was found.

Enter the search string or quit to exit.. AAron

AAron was not found

Enter the search string or quit to exit.. James

James was found.

Enter the search string or quit to exit.. Irvinf

Irvinf was not found

Enter the search string or quit to exit.. quit

quitting...

Kindly check the code output below.