Python Question - Computer Science

Part 1

Write a function called searchOrSort() that runs and times the following two experiments:

1. Create a random list of 1000 elements, and do 10000 linear searches on it.

2. Create a random list of 1000 elements, sort it once, and do 10000 binary searches on it.

Part 2

There are many different algorithms available for sorting a list of values. Here's the pseudocode of a sorting algorithm called GnomeSort:

gnomeSort(lis):

index = 0

while index is less than len(lis)

if index==0 or the item to the left is less than the item at index:

increment index

else:

swap lis[index] with lis[index-1]

decrement index

Write a function called gnomeSort() that performs this algorithm in python. Test that it correctly sorts any given list of random elements.