Standard Methods (CIE IGCSE Computer Science)

• The linear search is a standard algorithm used to find elements in an unordered list. The list is searched sequentially and systematically from the start to the end one element at a time, comparing each element to the value being searched for
• If the value is found the algorithm outputs where it was found in the list
• If the value is not found it outputs a message stating it is not in the list
• An example of using a linear search would be looking for a specific student name in a list or searching for a supermarket item in a shopping list

OUTPUT “Enter a value to find”

INPUT Number

Found ← FALSE

Index ←1

 

REPEAT

IF Number = Mylist[Index] 

             THEN

Found ← TRUE

ELSE

Counter ← Counter + 1

ENDIF

UNTIL Found =TRUE OR Counter > LENGTH(Mylist) 

 

IF Found = TRUE 

  THEN

OUTPUT Number, “ found at position “, Counter

ELSE

OUTPUT Number, “ not found”

ENDIF

• Bubble sort sorts items into order, smallest to largest, by comparing pairs of elements and swapping them if they are out of order
• The first element is compared to the second, the second to the third, the third to the fourth and so on, until the second to last is compared to the last. Swaps occur if each comparison is out of order. This overall process is called a pass
• Once the end of the list has been reached, the value at the top of the list is now in order and the sort resets back to the start of the list. The next largest value is then sorted to the top of the list
• More passes are completed until all elements are in the correct order
• A final pass checks all elements and if no swaps are made then the sort is complete
• An example of using a bubble sort would be sorting into alphabetical order an array of names, or sorting an array of student marks from a test

Mylist ← [5, 9, 4, 2, 6, 7, 1, 2, 4, 3]

FirstElement ← 1

LastElement ← LENGTH(Mylist)

REPEAT

Swap ← FALSE

For Index ← FirstElement TO LastElement - 1

IF Mylist[Index] > Mylist[Index + 1] 

  THEN

Temp ← Mylist[Index]

Mylist[Index] ← Mylist[Index + 1]

Mylist[Index + 1] ← Temp

Swap ← TRUE

ENDIF

NEXT Index

LastElement ← LastElement - 1

UNTIL Swap = FALSE OR LastElement = 1

OUTPUT “Your sorted list is:”, Mylist

Totalling

• Totalling involves keeping a running total of values entered into the algorithm. An example may be totalling a receipt for purchases made at a shop
• The Total below starts at 0 and adds up the user inputted value for each item in the list. For example, if the user has a receipt for four items: an apple (£0.50), a drink (£1), a sandwich (£2) and a bar of chocolate (£1). The algorithm will total the cost for each item one at a time. The output Total will be 4.50

Total ← 0

FOR Count ← 1 TO ReceiptLength

INPUT ItemValue

Total ← Total + itemValue

NEXT Count

OUTPUT Total

Counting

• Counting works similarly to totalling except the count is incremented or decremented by a fixed value, usually 1, each time it iterates. Counting keeps track of the number of times an action has been performed. Many algorithms use counting, including the linear search and binary search to track which element is currently being considered
• The count is incremented and each pass number is output until fifty outputs have been produced

Count ← 0

DO

OUTPUT “Pass number”, Count

Count ← Count + 1 

UNTIL Count >= 50

• The count is decremented from fifty until the count reaches zero. An output is produced for each pass

Count ← 50

DO

OUTPUT “Pass number”, Count

Count ← Count - 1

UNTIL Count <= 0

• Finding the largest and smallest values in a list is a frequently used method in algorithms. Examples could include the maximum and minimum student grades or scores in a game

Max ← Score[1]

Min ← Score[1]

 

FOR Count ← 2 TO ScoreSize

IF ScoreSize[Count] > Max

  THEN

Max ← ScoreSize[Count]

ENDIF

IF ScoreSize[Count] < Min

  THEN

Min ← ScoreSize[Count]

ENDIF

Next Count

• In the above algorithm, the initial max and min are set to the first value in the list and the for loop starts at the second element instead of the first as the first value is the benchmark to compare all other items to
• If no value is larger than the initial max, then Max doesn’t change. If no value is smaller than the initial min, then Min doesn’t change
• The algorithm loops over each element asking whether the current value is larger than Max and whether it is smaller than Min. Max and Min adjust their values throughout the program depending on these conditions
• The program will eventually output the smallest and largest value in Min and Max respectively

• Average values (also known as the mean) involve totalling all the list values and then dividing by the number of values in the list

Total ← 0

FOR Count ← 1 TO ScoreSize

Total ← Total + ScoreSize[Count]

NEXT Count

Average ← Total / ScoreSize