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

Pseudocode

Get a sorted list and a search term.

Loop through the sorted list:

Compare the item to the search term. 

If the search term matches the item:

    return the couter value

Add one to the counter

In [37]:
import random

The algorithm


In [112]:
# Simple brute force search engine

def ownsearch(sorted_list, search_term):
    counter = 0
    for i in sorted_list:
        if search_term == i:
            return "I found the term " + str(search_term) + " the first time at index " + str(counter)
        counter += 1

In [113]:
sorted_list = ['Alma', 'Annus', 'Mater', 'mirabilis']
search_term = 'Mater'

print(ownsearch(sorted_list,search_term))


I found the term Mater the first time at index 2

Testing the algorithm


In [114]:
# The algorithm from the previous assignment

def ownsort(int_list):
    for i in range(len(int_list) - 1):
        k = i
        for j in range(i + 1, len(int_list)):
            if int_list[j] < int_list[k]:
                k = j
        int_list[i], int_list[k] = int_list[k], int_list[i]
    return int_list

In [115]:
# Generate Lists with Random numbers 

int_list_10 = []
for i in range(0,10):
    int_list_10.append(random.randint(1,100))

int_list_100 = []
for i in range(0,100):
    int_list_100.append(random.randint(1,100))

int_list_1000 = []
for i in range(0,1000):
    int_list_1000.append(random.randint(1,100))

In [116]:
# Generating random int for search term

search_term = random.randint(1,100)

# Generating sorted list
int_list_10 = ownsort(int_list_10)

print(ownsearch(int_list_10, search_term))

%time


None
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 5.01 µs

Result of %time:

CPU times: user 0 ns, sys: 0 ns, total: 0 ns Wall time: 5.01 µs


In [117]:
# Generating random int for search term

search_term = random.randint(1,100)

# Generating sorted list
int_list_100 = ownsort(int_list_100)

print(ownsearch(int_list_100, search_term))

%time


I found the term 36 the first time at index 35
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 5.72 µs

In [ ]:
Result of %time:

CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 5.72 µs

In [118]:
# Generating random int for search term

search_term = random.randint(1,100)

# Generating sorted list
int_list_1000 = ownsort(int_list_1000)

print(ownsearch(int_list_1000, search_term))

%time


I found the term 11 the first time at index 105
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 5.01 µs

In [ ]:
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 5.01 µs