Question

Write a program that takes as input the following unsorted list of English words:

[Perfect, Stupendous, Wondrous, Gorgeous, Awesome, Mirthful, Fabulous, Splendid, Incredible, Outstanding, Propitious, Remarkable, Stellar, Unbelievable, Super, Amazing].

• Use linear search to find the position of Amazing, Perfect, Great, and Wondrous in the list. Also, note the number of key comparisons required to find these words in the list.
• Use a Python function to sort the list.
• Again, use linear search to determine the position of Amazing, Perfect, Great, and Wondrous in the list and note the number of key comparisons required to find these words in the list.
• Use binary search to determine the position of Amazing, Perfect, Great, and Wondrous in the sorted list. Record the number of iterations required in each case.

Answer 1

Linear Search without sorting:
def linearsearch(arr, x):
   for i in range(len(arr)):
      if arr[i] == x:
         return i
   return -1
arr = ["Perfect", "Stupendous", "Wondrous", "Gorgeous", "Awesome", "Mirthful", "Fabulous", "Splendid", "Incredible", "Outstanding", "Propitious", "Remarkable", "Stellar","Unbelievable", "Super", "Amazing"]
x = input("Enter key to be searched: ")
print("element found at index "+str(linearsearch(arr,x)+1))

• Amazing: Position = 16, number of comparisons = 16
• Perfect: Position = 1, number of comparisons = 1
• Great: Position = element not found.
• Wondrous: Position = 3, number of comparisons = 3

Linear Search after sorting:
def linearsearch(arr, x):
   for i in range(len(arr)):
      if arr[i] == x:
         return i
   return -1
arr = sorted(["Perfect", "Stupendous", "Wondrous", "Gorgeous", "Awesome", "Mirthful", "Fabulous", "Splendid", "Incredible", "Outstanding", "Propitious", "Remarkable", "Stellar","Unbelievable", "Super", "Amazing"])
print("Sorted list: ",arr)
x = input("Enter key to be searched: ")
print("element found at position "+str(linearsearch(arr,x)+1))

• Amazing: Position = 1, number of comparisons = 1
• Perfect: Position = 8, number of comparisons = 8
• Great: Position = element not found.
• Wondrous: Position = 16, number of comparisons = 16

Binary Search
def binary_search(arr, low, high, x):
    if high >= low:
        mid = (high + low) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)
        else:
            return binary_search(arr, mid + 1, high, x)
    else:
        return -1
arr =  sorted(["Perfect", "Stupendous", "Wondrous", "Gorgeous", "Awesome", "Mirthful", "Fabulous", "Splendid", "Incredible", "Outstanding", "Propitious", "Remarkable", "Stellar","Unbelievable", "Super", "Amazing"])
print(arr)
x = input("Enter the key to be searched: ")
result = binary_search(arr, 0, len(arr)-1, x)
if result != -1:
    print("Element is present at position", str(result+1))
else:
    print("Element is not present in array")

• Amazing: Position = 1
• Perfect: Position = 8
• Great: Position = element not found.
• Wondrous: Position = 16