Asignment 1

  • Implement the sorting algorithm you came up with in pseudocode with Python
  • Test the sorting algorithm with a list of 10, 100, 1000 random numbers and compare the result using the %time to time your code and submit your results in code comments

In [1]:
## pseudocode
# for number in a list:
#     put the first number of the list into the new list
#     for other numbers in the list
#     compare it with every number in the new list,get it's index number
#     if it's larger than any number in the new list, put it on the index+1 position

In [87]:
def get_sort(l):
    newlist = []
    newlist.append(l[0])
    for i in range(1,len(l)):
        added = False
        for m in range(len(newlist)):
            if l[i] > newlist[m]:
                added = False
            if added == False:
                if l[i] <= newlist[m]:
                    newlist.insert(m,l[i])
                    added = True 
        if added == False:
            newlist.append(l[i])
    return newlist

In [89]:
test10 = [4,5,8,1,3,5,22,14,50,23]
%time get_sort(test10)
# CPU times: user 25 µs, sys: 0 ns, total: 25 µs
# Wall time: 28.1 µs
# Out[79]:
# [1, 3, 4, 5, 5, 8, 14, 22, 23, 50]


CPU times: user 25 µs, sys: 0 ns, total: 25 µs
Wall time: 28.1 µs
Out[89]:
[1, 3, 4, 5, 5, 8, 14, 22, 23, 50]

In [80]:
import random

In [85]:
# test100 = random.sample(range(1, 1000), 100)
# %time get_sort(test100)
# CPU times: user 997 µs, sys: 20 µs, total: 1.02 ms
# Wall time: 1.05 ms

In [86]:
# test1000 = random.sample(range(1, 10000), 1000)
# %time get_sort(test1000)
# CPU times: user 128 ms, sys: 3.59 ms, total: 131 ms
# Wall time: 170 ms

In [94]:
sorted10 = get_sort(test10)
sorted100 = get_sort(test100)
sorted1000 = get_sort(test1000)

Assignment 2

  • Implement the search algorithm you came up with in pseudocode with Python
  • Test the search algorithm with a list of 10,100,1000 random numbers (sorted with your sorting algorithm) and compare the result using the %time to time your code and submit your results in code comments

In [ ]:
## pseudocode
# input a sorted list and a search term
#     get the length of the list
#     for each number in the range of length
#         if the index number of the list equals to the search term
#             print index
#             something = True
#         else 
#             something = False
#     if False
#         print the item is not found

In [121]:
def check_num(l,n):
    for i in range(len(l)):
#         print(l[i])
        found = False
        if l[i] == n:
            found = True
            return "The index of the number in the list is " + str(i)
    if not found:
        return "The number is not in the list."

In [122]:
%time check_num(sorted10,4)
# CPU times: user 7 µs, sys: 0 ns, total: 7 µs
# Wall time: 11.2 µs
# Out[122]:
# 'The index of the number in the list is 2'


CPU times: user 7 µs, sys: 0 ns, total: 7 µs
Wall time: 11.2 µs
Out[122]:
'The index of the number in the list is 2'

In [123]:
%time check_num(sorted100,4)
# CPU times: user 20 µs, sys: 0 ns, total: 20 µs
# Wall time: 23.1 µs
# Out[123]:
# 'The number is not in the list.'


CPU times: user 20 µs, sys: 0 ns, total: 20 µs
Wall time: 23.1 µs
Out[123]:
'The number is not in the list.'

In [127]:
%time check_num(sorted1000,9987)
# CPU times: user 120 µs, sys: 0 ns, total: 120 µs
# Wall time: 123 µs
# Out[127]:
# 'The index of the number in the list is 998'


CPU times: user 120 µs, sys: 0 ns, total: 120 µs
Wall time: 123 µs
Out[127]:
'The index of the number in the list is 998'

In [ ]: