In [2]:
def sort_list(listed):
# for each index number in the list starting at 1:
for i in range(1,len(listed)):
# set the current value equal to the value at index, i:
currentvalue = listed[i]
# print('current value:', currentvalue)
# set position to index of the current value
position = i
# print('position:', position)
# while the index number is greater than zero and the value before the current value
# is greater than the current value:
while position>0 and listed[position-1]>currentvalue:
# print('Index position', position, 'is greater than 0')
# print('The value at index position', position, 'is', listed[position])
# print ('And the value at index position', position-1, 'is', listed[position-1], 'which is greater than', currentvalue)
# print('We change the value of', listed[position], 'to', listed[position-1])
listed[position]=listed[position-1]
# print('We change the value of the variable storing index position from', position, 'to', position-1)
position = position-1
listed[position]=currentvalue
# print('Index position equals 0, so we exit the loop')
# print('And we set the value at index position', position, "to", currentvalue)
In [3]:
def search_list(listed, search_item):
# set start to index position zero
start = 0
# set end to last index position:
end = len(alist)-1
found = False
# while start index is less than or equal to end index and found is False:
while start<=end and not found:
# set middle to half the length of the list
middle = int((start + end)//2)
# if the value at the middle index position equals the search item:
if listed[middle] == search_item:
# set found equal to True
found = True
# if the value at the middle index position does not equal the search item:
else:
# if the search item is less than the value at the middle index:
if search_item < listed[middle]:
# then set end to index position middle-1
end = middle-1
# if the search item is greater than the value at the middle index:
else:
# then set start to index position middle+1
start = middle+1
# return found value, search item value, index position
return found, search_item, middle
In [7]:
import random
lengths=[10,100,1000]
for x in lengths:
alist = random.sample(range(x), x)
sort_list(alist)
%time search_list(alist, random.choice(alist))
# for a list length 10:
# CPU times: user 13 µs, sys: 1 µs, total: 14 µs
# Wall time: 14.8 µs
# for a list length 100:
# CPU times: user 15 µs, sys: 0 ns, total: 15 µs
# Wall time: 18.1 µs
# for a list length 1000:
# CPU times: user 17 µs, sys: 0 ns, total: 17 µs
# Wall time: 20 µs
In [ ]: