Why speed depends on the method
| Name | Doubling the data means | Example |
|---|---|---|
| O(1) | The same time | Reading list[5] |
| O(log n) | One extra step | Binary search |
| O(n) | Double the time | Checking each item |
| O(n log n) | A little over double | Merge sort |
| O(n²) | Four times the time | Bubble sort |
Stacks and queues
from collections import deque
stack = []
stack.append("a")
stack.append("b")
print(stack.pop()) # b: last in, first out
queue = deque()
queue.append("a")
queue.append("b")
print(queue.popleft()) # a: first in, first outOutput
b a
Searching
def linear_search(items, target):
for position, item in enumerate(items):
if item == target:
return position
return -1
def binary_search(items, target): # The list must be sorted
low, high = 0, len(items) - 1
while low <= high:
middle = (low + high) // 2
if items[middle] == target:
return middle
if items[middle] < target:
low = middle + 1 # Throw away the left half
else:
high = middle - 1 # Throw away the right half
return -1
numbers = [3, 8, 15, 23, 42, 57]
print(linear_search(numbers, 23))
print(binary_search(numbers, 23))
print(binary_search(numbers, 7))Output
3 3 -1
Sorting
def bubble_sort(items):
items = items.copy()
for end in range(len(items) - 1, 0, -1):
for i in range(end):
if items[i] > items[i + 1]:
items[i], items[i + 1] = items[i + 1], items[i] # Swap
return items
def merge_sort(items):
if len(items) <= 1:
return items
middle = len(items) // 2
left, right = merge_sort(items[:middle]), merge_sort(items[middle:])
merged, l, r = [], 0, 0
while l < len(left) and r < len(right):
if left[l] <= right[r]:
merged.append(left[l])
l += 1
else:
merged.append(right[r])
r += 1
return merged + left[l:] + right[r:]
print(bubble_sort([5, 2, 9, 1]))
print(merge_sort([5, 2, 9, 1]))
print(sorted([5, 2, 9, 1])) # In real code, just use thisOutput
[1, 2, 5, 9] [1, 2, 5, 9] [1, 2, 5, 9]
Linked lists and binary search trees
class Node:
def __init__(self, value):
self.value = value
self.next = None
first = Node(1)
first.next = Node(2)
first.next.next = Node(3)
current = first
while current:
print(current.value)
current = current.next
class Tree:
def __init__(self, value):
self.value, self.left, self.right = value, None, None
def insert(self, value):
side = "left" if value < self.value else "right"
child = getattr(self, side)
if child:
child.insert(value)
else:
setattr(self, side, Tree(value))
def in_order(self):
left = self.left.in_order() if self.left else []
right = self.right.in_order() if self.right else []
return left + [self.value] + right
root = Tree(8)
for number in [3, 10, 1, 6]:
root.insert(number)
print(root.in_order()) # Always comes out sortedOutput
1 2 3 [1, 3, 6, 8, 10]
Graphs
A graph is places joined by links, such as a map. Breadth-first search finds the route with the fewest steps. The search lessons in the What is AI module let you watch it run.
from collections import deque
roads = {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": ["F"], "E": ["F"], "F": []}
def shortest_path(start, goal):
queue = deque([[start]])
seen = {start}
while queue:
path = queue.popleft()
if path[-1] == goal:
return path
for next_place in roads[path[-1]]:
if next_place not in seen:
seen.add(next_place)
queue.append(path + [next_place])
print(shortest_path("A", "F"))Output
['A', 'B', 'D', 'F']
Finished reading?