2.3.1 Flashcards
time complexity of linear search
best average worst
O(1)
O(n)
O(n)
time complexity of binary search
best average worst
O(1)
O(log n)
O(log n)
time complexity of binary tree search
best average worst
O(1)
O(log n)
O(log n)
time complexity of bubble sort
best average worst
O(n)
O(n^2)
O(n^2)
time complexity of insertion sort
best average worst
O(n)
O(n^2)
O(n^2)
time complexity of merge sort
best average worst
O(n log n)
O(n log n)
O(n log n)
time complexity of quick sort
best average worst
O(n log n)
O(n log n)
O(n^2)
linear search
looks at every item in the list
only search that works on unordered lists
binary search
only works on an ordered list of items
gets midpoint of range of items
checks if higher or lower
can discard half of the range
gets midpoint of smaller range
keeps going til item is found
eventually only 1 item will be left
binary tree search
a rooted tree where the nodes are ordered. If order = ascending the nodes of the left subtree have lower values than the root, and to the nodes right have higher values than the root.
to be as efficient as a binary search, the tree must be BALANCED
balanced tree - all leaves are around the same distance from the root.
bubble sort
repeatedly going through a list of items, comparing consecutive pairs of items and swapping the items if they are in the wrong order
pass - a complete set through the list
comparison - 1 pair being compared
maximum passes = n - 1
insertion sort
building up a sorted sublist in the first part of the original list, while the remaining part of the list remains unsorted
card 1, card 2,3,4,5…
then compare card 2 to card 1
card 1,2 card 3,4,5…
then compare card 3 to card 2 if it is less than compare it to card 1
card 1,2,3 card 4,5…
making a sublist that is ordered
merge sort
keep splitting the list until each sublist only contains 1 item
these sublists are merged into sublists of 2
when the items merged they are ordered
this carries on until all items are in 1 list
uses divide and conquer
comapre list 1+2 and 3+4 at the same time
quick sort
you have a: piviot value, low marker, high marker
pick a piviot value (e.g. first value)
all items less than piviot value go before it
all items more than piviot value go after it
to do this the markers are used
low mark is moved up over values that are lower than the pivot value
Once the low mark reaches a value that is higher than the pivot value it stops
high mark is moved down over values that are higher than the pivot value
If the high mark reaches a value that is lower than the pivot value, the algorithm swaps the values of the low mark and the high mark.
The process continues until the high mark overlaps with the low mark, which indicates the new position for the pivot value. Sometimes the pivot value is already in that position.
then 2 new piviots are found in sublists (before and after new piviot place)
process repeats
what type of sort is this pseudocode?
FUNCTION ???_sort(items, start, end)
// Base case for recursion:
// The recursion will stop when the partition contains a single item
IF start >= end THEN
RETURN
// Otherwise recursively call the function
ELSE
pivot_value = items[start] // Set to first item in the partition
low_mark = start + 1 // Set to second position in the partition
high_mark = end // Set to last position in the partition
finished = False
// Repeat until low and high values have been swapped as needed
WHILE finished == False
// Move the left pivot
WHILE low_mark <= high_mark AND items[low_mark] <= pivot_value
low_mark = low_mark + 1 // Increment low_mark
ENDWHILE
// Move the right pivot
WHILE low_mark <= high_mark and items[high_mark] >= pivot_value
high_mark = high_mark - 1 // Decrement high_mark
ENDWHILE
// Check that the low mark doesn't overlap with the high mark
IF low_mark < high_mark THEN
// Swap the values at low_mark and high_mark
temp = items[low_mark]
items[low_mark] = items[high_mark]
items[high_mark] = temp
// Otherwise end the loop
ELSE
finished = True
ENDIF
ENDWHILE
// Swap the pivot value and the value at high_mark
temp = items[start]
items[start] = items[high_mark]
items[high_mark] = temp
// Recursive call on the left partition
???_sort(items, start, high_mark - 1)
// Recursive call on the right partition
???_sort(items, high_mark + 1, end)
ENDIF
RETURN items ENDFUNCTION
quick sort
what type of sort is this pseudocode?
FUNCTION ???(left, right)
???_size = LEN(left) + LEN(right) // Size of the new array
ARRAY ???[???_size] // New array for ???the items
index_left = 0 // left current position
index_right = 0 // right current position
index_??? = 0 // ??? current position
// While there are still items to ???
WHILE index_left < LEN(left) AND index_right < LEN(right)
// Find the lowest of the two items being compared
// and add it to the new array
IF left[index_left] < right[index_right] THEN
???[index_merged] = left[index_left]
index_left = index_left + 1
index_??? = index_??? + 1
ELSE
???[index_???] = right[index_right]
index_right = index_right + 1
index_??? = index_??? + 1
ENDIF
ENDWHILE
// Add to the ??? array any remaining data from left array
WHILE index_left < LEN(left)
???[index_???] = left[index_left]
index_left = index_left + 1
index_??? = index_??? + 1
ENDWHILE
// Add to the ??? array any remaining data from right array
WHILE index_right < LEN(right)
???[index_???] = right[index_right]
index_right = index_right + 1
index_??? = index_??? + 1
ENDWHILE
RETURN ???
ENDFUNCTION
merge sort
what type of sort is this pseudocode?
PROCEDURE ???ion_sort(items)
// Initialise the variables
num_items = LEN(items)
// Repeat for each item in the list, starting at the second item
FOR index = 1 TO num_items - 1
// Get the value of the next item to ???
item_to_??? = items[index]
// Get the current position of the last sorted item
position = index - 1
// Repeat while there are still items in the list to check
// and the current sorted item is greater than the item to ???
WHILE position >= 0 AND items[position] > item_to_???
// Copy the value of the sorted item up one place
items[position + 1] = items[position]
// Get the position of the next sorted item
position = position - 1
ENDWHILE
// Copy the value of the item to ??? into the correct position
items[position + 1] = item_to_???
NEXT index ENDPROCEDURE
insertion sort
what type of sort is this pseudocode?
PROCEDURE ???_sort(items)
// Initialise the variables
num_items = LEN(items)
swapped = True
pass_num = 1
// Repeat while one or more swaps have been made
WHILE swapped == True
swapped = False
// Perform a pass, reducing the number of comparisons each time
FOR index = 0 TO num_items - 1 - pass_num
// Compare items to check if they are out of order
IF items[index] > items[index + 1] THEN
// Swap the items
temp = items[index]
items[index] = items[index + 1]
items[index + 1] = temp
swapped = True
ENDIF
NEXT index
pass_num = pass_num + 1
ENDWHILE ENDPROCEDURE
bubble sort
what type of search is this pseudocode?
FUNCTION search(node, search_item)
// Base case for recursion:
// The recursion will stop if the search item has been found
IF search_item == node.data THEN
RETURN True
// Check if the search item is greater than the node data
// and there is another node to the right to check
ELSEIF search_item > node.data AND node.right != Null THEN
RETURN search(node.right, search_item)
// Check if the search item is less than the node data
// and there is another node to the left to check
ELSEIF search_item < node.data AND node.left != Null THEN
RETURN search(node.left, search_item)
// Otherwise the search item does not exist
ELSE
RETURN False
ENDIF ENDFUNCTION
binary tree search
what type of search is this pseudocode?
FUNCTION ???_search(items, search_item)
// Initialise the variables
found = False
found_index = -1
first = 0
last = LEN(items) - 1
// Repeat while there are still items between first and last
// and the search item has not been found
WHILE first <= last AND found == False
// Find the midpoint position (in the middle of the range)
midpoint = (first + last) DIV 2
// Compare the item at the midpoint to the search item
IF items[midpoint] == search_item THEN
// If the item has been found, store the midpoint position
found_index = midpoint
found = True // Raise the flag to stop the loop
// Check if the item at the midpoint is less than the search item
ELSEIF items[midpoint] < search_item THEN
// Focus on the items after the midpoint
first = midpoint + 1
// Otherwise the item at the midpoint is greater than the search item
ELSE
// Focus on the items before the midpoint
last = midpoint - 1
ENDIF
ENDWHILE
// Return the position of the search_item or -1 if not found
RETURN found_index
ENDFUNCTION
binaery search
what type of search is this pseudocode?
FUNCTION ???_search_version_1(items, search_item)
// Initialise the variable
found_index = -1
// Repeat until the end of the list is reached
FOR current = 0 TO LEN(items) - 1
// Compare the item at the current index to the search item
IF items[current] == search_item THEN
// If the item has been found, store the current index
found_index = current
ENDIF
NEXT current
// Return the index of the search_item or -1 if not found
RETURN found_index ENDFUNCTION
linear search
Dijkstra’s algorithm
A* algorithm
builds on the principles of Dijkstra’s shortest path algorithm to provide a faster solution when faced with the problem of finding the shortest path between two nodes. It achieves this by introducing a heuristic element
A* algorithm differs from Dijkstra’s in that it seeks only the shortest path between the start node and the target node.
