Section 12 Algorithms

Question 1

linear search

Answer 1

traverses through every item 1 at a time until item is found

Question 2

Binary search algorithm

Answer 2

Divide and conquer so list is split into smaller lists until it finds the item it’s searching for

Question 3

Bubble sort algorithm

Answer 3

Passes through the list evaluating item pairs and ensuring the larger value is above the smaller value

Question 4

size()

Answer 4

Returns the number of elements on the stack
Returns the value of the top pointer plus one

size()
return top + 1

Question 5

isEmpty()

Answer 5

● Returns True if the stack is empty, otherwise returns False
● Works by checking whether the top pointer is less than 0

isEmpty()
if top < 0:
return True
else:
return False
endif

Question 6

peek()

Answer 6

● Returns the item at the top of the stack, without removing it
● Returns the item at the position indicated by the top pointer
● Important to check that the stack has data in it before attempting to return anything
peek()
if isEmpty():
return error
else:
return A[top]
endif

Question 7

push(element)

Answer 7

● Adds an item to a stack
● The new item must be passed as a parameter
● Firstly, the top pointer is updated accordingly
● Then the new element can be inserted at the position of the top pointer

push(element)
top += 1
A[top] = element

Question 8

pop()

Answer 8

● Removes an item from a stack
● Element at the position of the top pointer is recorded before being removed
● Top pointer decremented by one
● The removed item is returned
● As with peek()​, it’s important to first check that the stack isn’t empty

pop()
if isEmpty():
return error
else:
toRemove = A[top]
A[top] = “”
top -= 1
return toRemove
endif

Question 9

size()of queue

Answer 9

● Returns the number of elements in a queue
● Simply subtracts the value of front from back

size()
return back - front

Question 10

isEmpty()
queue

Answer 10

● Returns True if a queue is empty, and False otherwise
● When a queue is empty, front and back point to the same position.

isEmpty()
if front == back:
return True
else:
return False
endif

Question 11

peek()

Answer 11

peek()
● Returns the element at the front of the queue without removing it

peek()
return A[front]

Question 12

enqueue(element)

Answer 12

● Adds an element to the back of a queue
● The new element is placed in the position of back
● Back is incremented by one

enqueue(element)
A[back] = element
back += 1

Question 13

dequeue()

Answer 13

● Removes the item at the front of the queue
● Items are removed from a queue from the position of the front pointer
● Just as with stacks, it’s important to check that the queue isn’t empty
● After the element has been removed, the front pointer must be incremented

dequeue()
if isEmpty():
return error
else:
toDequeue = A[front]
A[front] = “”
front += 1
return toDequeue
endif

Question 14

Describe bubble sort

Answer 14

Makes comparisons and swaps between pairs of elements
● The largest element in the unsorted part of the input is said to “bubble” to the top of
the data with each iteration of the algorithm
○ Starts at the first element in an array and compares it to the second
○ If they are in the wrong order, the algorithm swaps the pair
○ The process is then repeated for every adjacent pair of elements in the array,
until the end of the array is reached
● This is one pass of the algorithm
● For an array with n elements, the algorithm will perform n passes through the data
● After n passes, the input is sorted and can be returned

Question 15

Bubble sort algorithm

Answer 15

A = ​Array of data
for i = 0 to A.length - 1:
for j = 0 to A.length - 2:
if A[j] > A[j+1]:
swap A[j] and A[j+1]
return A

Question 16

Modify bubble sort for improved efficiency

Answer 16

● Can be modified to improve efficiency
● A flag recording whether a swap has occurred is introduced
● If a full pass is made without any swaps, then the algorithm terminates
● With each pass, one fewer element needs comparing as the n largest elements are
in position after the nth pass

Question 17

Describe insertion sort

Answer 17

● Places elements into a sorted sequence
● In the i​th iteration of the algorithm the first i​ elements of the array are sorted
○ Warning: although the i​ elements are sorted, they are not the i​smallest
elements in the input!
● Stars at the second element in the input, and compares it to the element to its left
● When compared, elements are inserted into the correct position in the sorted
portion of the input to their left
● This continues until the last element is inserted into the correct position, resulting in
a fully sorted array

Question 18

Insertion sort algorithm

Answer 18

A = ​Array of data
for i = 1 to A.length - 1:
elem = A[i]
j = i - 1
while j > 0 and A[j] > elem:
A[j+1] = A[j]
j = j - 1
A[j+1] = elem

Question 19

Binary search algorithm

Answer 19

A ​= Array of data
x ​= Desired element

low = 0
high = A.length -1
while low <= high:
mid = (low + high) / 2
if A[mid] == x:
return mid
else if A[mid] > x:
high = mid -1
else:
low = mid + 1
endif
endwhile
return “Not found in data”

Question 20

Linear Search

Answer 20

● The most basic searching algorithm
● Looks at elements one at a time until the desired element is found
● Doesn’t require the data to be sorted
● A great deal of pot luck, but easy to implement
○ Sometimes gets lucky and finds the desired element almost immediately
○ In other situations, the algorithm is incredibly inefficient

Question 21

Linear search algorithm

Answer 21

A ​= Array of data
x ​= Desired element

i = 0
while i < A.length:
if A[i] == x:
return i
else:
i = i + 1
endif
endwhile
return “Not found in data”