Search routines (paper 2)

Question 1

what happens in a linear search

Answer 1

each item to be searched from will be checked one by one in the list until the item is found or an error is outputted

Question 2

what are the two types of search

Answer 2

• linear
• bubble sort

Question 3

What is the code for a linear search algorithm

Answer 3

// perform a linear search of an array
DECLARE AList : ARRAY[1:10] OF INTEGER
AList <- [14, 2, 3 ,11, 1, 9, 5, 8, 10, 6]
OUTPUT “List to be searched:”, AList
Found <- FALSE
Index <- 1
INPUT SearchItem
WHILE Found = FALSE AND Index <= LENGTH(AList) DO
IF AList[Index] = SearchItem
THEN
Found <- TRUE
ELSE
Index <- Index + 1
ENDIF
ENDWHILE
IF Found = TRUE
THEN
OUTPUT SearchItem, “in position”, Index, “of the list”
ELSE
OUTPUT “Item not found”
ENDIF

Question 4

what happens in a bubble sort

Answer 4

it repeatedly goes through the list to be sortedd, swapping adjacent elements if they are in the wrong order

Question 5

what is the pseudocode for a bubble sort

Answer 5

//bubble sort with flag set when no swaps are made
AList <-[17, 3, 7, 15, 12, 23, 20]
// get number of items in the array
NumItems <- LENGTH(AList)
Comparisions <- NumItems - 1
SwapMade <- TRUE
WHILE Comparisons > 0 AND SwapMade = TRUE
SwapMade <- FALSE
FOR i <- 1 TO Comparisons
IF AList[i] > AList[i + 1]
THEN
Temp <- AList[i]
AList[i] <- AList[i + 1]
AList[i + 1] <- Temp
SwapMade <- TRUE
ENDIF
NEXT i
Comparisons <- Comparisons - 1
ENDWHILE
OUTPUT “Sorted list: “, AList