Chapter 19 Flashcards
"Computational thinking and Problem-Solving"
linear search
loops and searches each element until the target is located
time: O(n), as time to search increases linearly in relation to the number of items in the list
space: O(1), constant amount of space
linear search python
def linearsearch(arr, target):
for i in range(len(arr)):
if arr[i] == target:
print("Target found")
return i
print("Target not found")
return -1binary search
- find the middle item
- check if value of middle item is equal to the target
- if equal target is found
- if not, compare if target is greater or lesser than mid, and discard the half of the list that doesn’t contain the target
- repeat the above steps until the target is found
- or low == high and target is still not found, then target is not in the list
time is o(log n) as the array is divided in half at each step
space is o(1) as it uses a constant amount of extra space
conditions necessary for a binary search
the list needs to be ordered
binary search python
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high)//2
if arr[mid] == target:
print(f"target at index {mid}")
break
elif target > arr[mid]:
low = mid + 1
elif target < arr[mid]:
high = mid - 1insertion sort
swaps/orders in one iteration by inserting data in correct place
uses less memory and time than bubble sort
time is o(n^2)
space is o(1) as it uses a constant amount of extra space
insertion sort python
for i in range(1, len(list)):
cIndex = i
while (cIndex > 0) and (list[cIndex - 1] > list[cIndex]):
list[cIndex], list[cIndex - 1] = list[cIndex - 1], list[cIndex]
cIndex -= 1
- cIndex = current index
- starts at one because list compares with previous, not post (post in bubble sort). 0th place will be swapped to correct position, 0-1 will cause error
- checks all elements before the “element to be inserted” are in the correct position, then moves on
- index increments, then the currentIndex (while not at the beginning of the list and while the elements before are unsorted (c-1 > c) checks all those before it if the swap has changed the order
- while loop works backwards
bubble sort
Bubble sort compares adjacent elements in the list/array.
They are swapped if the elements are in the wrong order
The algorithm iterates through the array multiple times in passes, using a swap flag
On each pass, the largest unsorted element gets sorted to its correct position at the end of the array.
The process is repeated until the entire array is sorted.
bubble sort python
for i in range(len(array) - 1): #-1 for zero indexing
swapped = False
for j in range(len(array)-i-1): #compares all adjacent pairs. i stays the same during this inner loop, j increments
if array[j] > array[j +1]:
array[j], array[j+1] = array[j+1], array[j]
swapped = True
if swapped is False:
break ADTs and examples
Abstract Data Type
linked list
queue
stack
binary tree
linked list
a dynamic data structure of nodes and pointers, where items are not stored contiguously in memory.
the first node is the head, the last node is the tail
binary tree
an ADT with nodes arranged hierarchally starting with root at top, where each node has 2 descendants.
left pointer -> left subtree, right pointer -> right subtree
three modes of traversal:
- in order
- preorder
- post order
post order traversal
- post order moves from the bottom of the tree up - left subtree, right subtree, then the root node. prints after seeing the node three times
python:
def postorder(self):
if self.left is not None:
self.left.postorder()
if self.right is not None:
self.right.postorder()
print(self.data)
pre order traversal
- pre order visits the root node first, then the left subtree, then the right. prints after seeing the node for the first time.
python:
def preorder(self):
print(self.data) #prints first node it sees
if self.left is not None:
self.left.preorder()
if self.right is not None:
self.right.preorder()
in order traversal
using 2D arrays
- in order traversal prints the binary tree in order of ascending node data. prints after the program has seen the node twice.
- procedure InOrder taking a parameter (current node being accessed)
- Checking if left Node is empty (−1 or None)
- ….if not empty, calls procedure recursively with left node as parameter
- if it is empty, outputs the current node
- checks if right Node is empty (−1 or None)
- …if not empty, calls procedure recursively with right node as a parameter
- Order is correct, left, root, right
def InOrder(ArrayNodes, RootNode):
if ArrayNodes[RootNode][0] != -1: #if left node is not empty
InOrder(ArrayNodes, ArrayNodes[RootNode][0]) #recursively call to search left node
print(str(ArrayNodes[RootNode][1])) #print current node
if ArrayNodes[RootNode][2] != -1:
InOrder(ArrayNodes, ArrayNodes[RootNode][2])
def inorder(self): #in order traversal, with printing data
if self.left is not None:
self.left.inorder() #keeps calling as long as there is a left node to search,
print(self.data) #then prints. starts from smallest to largest
if self.right is not None: #unwinds, searches right subtree of "previous" node
self.right.inorder()
