Answer:
Check the explanation
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.
Answer:
See explaination for program code
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)
