Section 12 Algorithms Flashcards
linear search
traverses through every item 1 at a time until item is found
Binary search algorithm
Divide and conquer so list is split into smaller lists until it finds the item it’s searching for
Bubble sort algorithm
Passes through the list evaluating item pairs and ensuring the larger value is above the smaller value
size()
Returns the number of elements on the stack
Returns the value of the top pointer plus one
size()
return top + 1
isEmpty()
● 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
peek()
● 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
push(element)
● 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
pop()
● 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
size()of queue
● Returns the number of elements in a queue
● Simply subtracts the value of front from back
size()
return back - front
isEmpty()
queue
● 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
peek()
peek()
● Returns the element at the front of the queue without removing it
peek()
return A[front]
enqueue(element)
● 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
dequeue()
● 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
Describe bubble sort
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
Bubble sort algorithm
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
Modify bubble sort for improved efficiency
● 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
Describe insertion sort
● Places elements into a sorted sequence
● In the ith iteration of the algorithm the first i elements of the array are sorted
○ Warning: although the i elements are sorted, they are not the ismallest
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
Insertion sort algorithm
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
Binary search algorithm
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”
Linear Search
● 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
Linear search algorithm
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”
