2.3.1

Question 1

time complexity of linear search

best average worst

Answer 1

O(1)
O(n)
O(n)

Question 2

time complexity of binary search

best average worst

Answer 2

O(1)
O(log n)
O(log n)

Question 3

time complexity of binary tree search

best average worst

Answer 3

O(1)
O(log n)
O(log n)

Question 4

time complexity of bubble sort

best average worst

Answer 4

O(n)
O(n^2)
O(n^2)

Question 5

time complexity of insertion sort

best average worst

Answer 5

O(n)
O(n^2)
O(n^2)

Question 6

time complexity of merge sort

best average worst

Answer 6

O(n log n)
O(n log n)
O(n log n)

Question 7

time complexity of quick sort

best average worst

Answer 7

O(n log n)
O(n log n)
O(n^2)

Question 8

linear search

Answer 8

looks at every item in the list
only search that works on unordered lists

Question 9

binary search

Answer 9

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

Question 10

binary tree search

Answer 10

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.

Question 11

bubble sort

Answer 11

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

Question 12

insertion sort

Answer 12

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

Question 13

merge sort

Answer 13

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

Question 14

quick sort

Answer 14

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

Question 15

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

Answer 15

quick sort

Question 16

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

Answer 16

merge sort

Question 17

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

Answer 17

insertion sort

Question 18

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

Answer 18

bubble sort

Question 19

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

Answer 19

binary tree search

Question 20

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

Answer 20

binaery search

Question 21

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

Answer 21

linear search

Question 22

Dijkstra’s algorithm

Question 23

A* algorithm

Answer 23

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.