Types of Algorithms

Question 1

Features of a bubble sort

Answer 1

• Uses an incremental approach
• Slow and inefficient
• Not for large lists
• Simple to understand

Question 2

n = items.length
swapped = True

while n > 0 AND swapped - False
n = n - 1
for index = 0 to n - 1
if items [index] > items [index + 1] then
swap (items[index], items[index+1])
swapped = True
end if
end for
end while

Answer 2

Bubble Sort Psuedocode

Question 3

Features of an insertion sort

Answer 3

• Uses an incremental approach

Question 4

for index = 1 to items.length:
current = items[index]
index2 = index

while index2 > 0 AND items[index2 - 1] > current
items[index2] = items[index2 - 1]
index2 = index2 = 1
end while

items[index2] = current
end for

Answer 4

Insertion Sort Pseudocode

Question 5

Features of a linear search

Answer 5

• Start at the beginning of the list
• Compare search value to 1st item
• Can be an unordered list

Question 6

found = False
index = 0
while found == False AND index < items.length
if items[index] == item_to_find then
found = True
else
index = index + 1
end if
end while

Answer 6

Linear Search Pseudocode

Question 7

Features of binary search

Answer 7

• List must be ordered
• Split list in half

Question 8

found = False
first = 0
last = items.length - 1

while first <= last AND found == False
midpoint = (first + last) DIV 2
if items[midpoint] == item_to_find then
found = True
else
if items[midpoint] < item_to_find then
first = midpoint + 1
else
last = midpoint - 1
end if
end if
end while

Answer 8

Binary Search Pseudocode