2.3.1 - algorithms

Question 1

algorithm

Answer 1

A set of rules or a sequence of steps specifying how to solve a problem.

Question 2

2 searching algorithms

Answer 2

• linear search
• binary search

Question 3

linear search pseudocode

Answer 3

function LinearSearch(alist,itemSought}
index = -1
i = 0
found = False
while i < length(alist) and found = False
if alist[iI = itemSought then
index = i
found = True
endif
i = i + 1
endwhile
return index
endfunction

Question 4

linear search

Answer 4

If the items are not in any particular sequence, the data items have to be searched one by one until the required one is found or the end of the list is reached.

Question 5

binary search

Answer 5

The algorithm works by repeatedly dividing in half the portion of the SORTED data list that could contain the required data item. This is continued until there is only one item in the list.

Question 6

binary search pseudocode

Answer 6

function binarySearch(aList, itemSought}
found = False
index = -1
first = C
last = len (aList)-1
while first <= last and found = False
midpoint = Integer part of ((first + last)/2)
if aList[midpoint) = itemSought then
found = True
index = midpoint
else
if aList(midpoint) < itemSought then
first = midpoint + l
else
last = midpoint - i
endif
endif
endwhile
return index
endfunction

Question 7

bubble sort

Answer 7

• Go through the array, comparing each item with the one next to it. If it is greater, swap them.
• The last element of the array will be in the correct place after the first pass
• Repeat n-2 times, reducing by one on each pass the number of elements to be examined

Question 8

bubble sort pseudocode

Answer 8

numItems = len(numbers)
for i = 0 to numItems - 2
for j = 0 to(numItems - i - 2)
if numbers [j] > numbers [j + 1]
temp = numbers[j]
numbers [ j ] = numbers[ j + 1]
numbers [j+1] = temp
endif
next j
print (numbers)
next i

Question 9

insertion sort

Answer 9

The algorithm takes one data item
from the list and places It in the correct location in the list. This process is
repeated until there are no more unsorted data items in the list.

Question 10

insertion sort pseudocode

Answer 10

procedure inaertionSort(alist)
n = len(alist)
for index = 1 to n - 1
currentvalue = alist[index]
position = index
while position > 0 and alist[position - l| >
currentvalue
alist(position] = alist[position - 1]
position = position - l
endwhile
alist(position) = currentvalue
next index
endprocedure