Searching and sorting; validation and verification

Totalling and counting

Totalling means adding values into a running total: `Total ← Total + Value`.

Counting means adding 1 each time something happens: `Count ← Count + 1`.

Both variables must start at 0 before the loop.

DECLARE Marks : ARRAY[1:6] OF INTEGER
DECLARE Index : INTEGER
DECLARE Total : INTEGER
DECLARE PassCount : INTEGER
// Marks already holds 34, 48, 21, 40, 15, 45
Total ← 0
PassCount ← 0
FOR Index ← 1 TO 6
  Total ← Total + Marks[Index]
  IF Marks[Index] >= 25
    THEN
      PassCount ← PassCount + 1
  ENDIF
NEXT Index
OUTPUT "Total: ", Total
OUTPUT "Number of passes: ", PassCount

marks = [34, 48, 21, 40, 15, 45]
total = 0
pass_count = 0
for index in range(6):
    total = total + marks[index]
    if marks[index] >= 25:
        pass_count = pass_count + 1
print("Total:", total)
print("Number of passes:", pass_count)

Finding the maximum and minimum

To find the maximum (largest), keep a variable `Highest`. Compare each value with it. If the value is bigger, it becomes the new `Highest`.

The minimum (smallest) works the same way with `Lowest` and `<`.

Start `Highest` at the smallest possible value and `Lowest` at the largest possible value. Another safe way is to start both at the first item.

DECLARE Marks : ARRAY[1:6] OF INTEGER
DECLARE Index : INTEGER
DECLARE Highest : INTEGER
DECLARE Lowest : INTEGER
// Marks already holds 34, 48, 21, 40, 15, 45 (each out of 50)
Highest ← 0
Lowest ← 50
FOR Index ← 1 TO 6
  IF Marks[Index] > Highest
    THEN
      Highest ← Marks[Index]
  ENDIF
  IF Marks[Index] < Lowest
    THEN
      Lowest ← Marks[Index]
  ENDIF
NEXT Index
OUTPUT "Highest: ", Highest
OUTPUT "Lowest: ", Lowest

marks = [34, 48, 21, 40, 15, 45]
highest = 0
lowest = 50
for index in range(6):
    if marks[index] > highest:
        highest = marks[index]
    if marks[index] < lowest:
        lowest = marks[index]
print("Highest:", highest)
print("Lowest:", lowest)

Finding the average

The average (mean) is the total divided by how many values there are.

First total the values in a loop. Then divide once, after the loop.

The answer is usually not a whole number, so store it as `REAL`. Use `ROUND` to give a set number of decimal places.

DECLARE Marks : ARRAY[1:6] OF INTEGER
DECLARE Index : INTEGER
DECLARE Total : INTEGER
DECLARE Average : REAL
// Marks already holds 34, 48, 21, 40, 15, 45
Total ← 0
FOR Index ← 1 TO 6
  Total ← Total + Marks[Index]
NEXT Index
Average ← Total / 6
OUTPUT "Average: ", ROUND(Average, 2)

marks = [34, 48, 21, 40, 15, 45]
total = 0
for index in range(6):
    total = total + marks[index]
average = total / 6
print("Average:", round(average, 2))

Linear search

A linear search looks for a value by checking each item in a list, one at a time, from the start.

It stops when it finds the item, or when it reaches the end of the list.

Try it: the toy's list holds numbers, not names. Type 22 (the last item), press Search for it, then Run all. Then try 99, which is not there. Count the comparisons each time.

DECLARE Names : ARRAY[1:6] OF STRING
DECLARE Target : STRING
DECLARE Index : INTEGER
DECLARE Found : BOOLEAN
// Names already holds Lucia, Hugo, Martina, Pablo, Sofia, Leo
OUTPUT "Which name do you want to find? "
INPUT Target
Found ← FALSE
Index ← 1
WHILE Found = FALSE AND Index <= 6 DO
  IF Names[Index] = Target
    THEN
      Found ← TRUE
    ELSE
      Index ← Index + 1
  ENDIF
ENDWHILE
IF Found = TRUE
  THEN
    OUTPUT Target, " found at position ", Index
  ELSE
    OUTPUT Target, " is not in the list"
ENDIF

names = ["Lucia", "Hugo", "Martina", "Pablo", "Sofia", "Leo"]
target = input("Which name do you want to find? ")
found = False
index = 0
while found == False and index < 6:
    if names[index] == target:
        found = True
    else:
        index = index + 1
if found == True:
    print(target, "found at position", index + 1)
else:
    print(target, "is not in the list")

There is something to try for this step in the IGCSE library.

Bubble sort

A bubble sort puts a list in order. It compares each pair of neighbours. If they are in the wrong order, it swaps them.

One trip through the list is a pass. After each pass the largest unsorted value has 'bubbled' to the end.

It stops when a pass makes no swaps. The toy uses a longer list: 6, 2, 9, 4, 7, 1, 5. Press Reset, then Step one comparison at a time. Watch the 9 move to the end in pass 1.

DECLARE Numbers : ARRAY[1:5] OF INTEGER
DECLARE Top : INTEGER
DECLARE Index : INTEGER
DECLARE Temp : INTEGER
DECLARE Swap : BOOLEAN
Numbers[1] ← 7
Numbers[2] ← 3
Numbers[3] ← 9
Numbers[4] ← 2
Numbers[5] ← 5
Top ← 5
REPEAT
  Swap ← FALSE
  FOR Index ← 1 TO Top - 1
    IF Numbers[Index] > Numbers[Index + 1]
      THEN
        Temp ← Numbers[Index]
        Numbers[Index] ← Numbers[Index + 1]
        Numbers[Index + 1] ← Temp
        Swap ← TRUE
    ENDIF
  NEXT Index
  Top ← Top - 1
UNTIL Swap = FALSE OR Top = 1

# Python has no REPEAT ... UNTIL, so a WHILE loop is used
numbers = [7, 3, 9, 2, 5]
top = 5
swap = True
while swap == True and top > 1:
    swap = False
    for index in range(top - 1):
        if numbers[index] > numbers[index + 1]:
            temp = numbers[index]
            numbers[index] = numbers[index + 1]
            numbers[index + 1] = temp
            swap = True
    top = top - 1
print(numbers)

There is something to try for this step in the IGCSE library.

How many comparisons? (extra)

This formula is not in the syllabus. It is useful for understanding why bubble sort is slow for long lists.

In the worst case every pass is needed. With n items, pass 1 makes n − 1 comparisons, pass 2 makes n − 2, and so on down to 1.

Adding these gives n(n − 1) ÷ 2. Double the list and the work goes up about four times.

Validation and verification are different

Validation is an automatic check by the program that data is reasonable and follows set rules. It happens on input.

Verification checks that data has been copied or typed correctly from the source. It does not check if the data is sensible.

You need both. Validation accepts an age of 15 even if the student is 16. Verification catches that typing mistake.

Range, length, type and presence checks

Range check: a number must be between a lowest and a highest value. Example: an exam mark from 0 to 100.

Length check: the number of characters must be exact or within limits. Example: a password of 8 to 20 characters.

Type check: data must be the right data type. Example: an age must be a whole number, not 'ten'. Presence check: something must be entered. The field cannot be left blank.

DECLARE UserName : STRING
DECLARE Password : STRING
// presence check: something must be typed
OUTPUT "Enter your name: "
INPUT UserName
WHILE UserName = "" DO
  OUTPUT "Error: the name cannot be blank. Enter your name: "
  INPUT UserName
ENDWHILE
// length check: 8 to 20 characters
OUTPUT "Choose a password (8 to 20 characters): "
INPUT Password
WHILE LENGTH(Password) < 8 OR LENGTH(Password) > 20 DO
  OUTPUT "Error: use 8 to 20 characters. Try again: "
  INPUT Password
ENDWHILE

user_name = input("Enter your name: ")
# presence check: something must be typed
while user_name == "":
    user_name = input("Error: the name cannot be blank. Enter your name: ")
# length check: 8 to 20 characters
password = input("Choose a password (8 to 20 characters): ")
while len(password) < 8 or len(password) > 20:
    password = input("Error: use 8 to 20 characters. Try again: ")
print("Welcome,", user_name)

Format and check digit checks

Format check: data must follow a set pattern of characters. Example: a Spanish DNI is 8 digits then 1 letter, like `12345678Z`.

Check digit: an extra digit worked out from the other digits and added to the end. The computer recalculates it. If the answers differ, there is an entry error.

Try the toy: type in each box of the form and watch its checks pass or fail. Press Fill with valid data, then change the Student ID to break the format check. Type 9780140449136 in the ISBN box, then change one digit to break the check digit.

There is something to try for this step in the IGCSE library.

Writing a validation loop

A validation loop asks for input, checks it, and asks again until it passes.

Use `REPEAT … UNTIL` or `WHILE … ENDWHILE`. Always give an error message that says what is allowed.

Python can also do a type check. `isdigit()` returns True only if every character is a digit.

DECLARE Age : INTEGER
REPEAT
  OUTPUT "Enter your age (11 to 18): "
  INPUT Age
  IF Age < 11 OR Age > 18
    THEN
      OUTPUT "Error: age must be from 11 to 18"
  ENDIF
UNTIL Age >= 11 AND Age <= 18
OUTPUT "Age accepted: ", Age

entry = input("Enter your age (11 to 18): ")
# presence, type and range checks, repeated until the entry passes
while entry == "" or not entry.isdigit() or int(entry) < 11 or int(entry) > 18:
    print("Error: enter a whole number from 11 to 18")
    entry = input("Enter your age (11 to 18): ")
age = int(entry)
print("Age accepted:", age)

Verification: visual check and double entry

A visual check means the user reads the data on screen and compares it with the original document. Example: checking a delivery address before you pay.

A double entry check means the data is typed twice. The computer compares the two entries. If they differ, it asks again.

Double entry is used for new passwords and email addresses, where you cannot see a mistake.

DECLARE Password : STRING
DECLARE Confirm : STRING
REPEAT
  OUTPUT "Enter a new password: "
  INPUT Password
  OUTPUT "Enter the same password again: "
  INPUT Confirm
  IF Password <> Confirm
    THEN
      OUTPUT "The two entries do not match. Start again."
  ENDIF
UNTIL Password = Confirm
OUTPUT "Password saved"

password = input("Enter a new password: ")
confirm = input("Enter the same password again: ")
while password != confirm:
    print("The two entries do not match. Start again.")
    password = input("Enter a new password: ")
    confirm = input("Enter the same password again: ")
print("Password saved")

The four types of test data

Normal data: data that should be accepted. It is well inside the range.

Abnormal data: data that should be rejected. It is outside the range or the wrong type.

Extreme data: the largest and smallest values that should be accepted. Boundary data: the largest and smallest accepted values and the nearest values outside the range, which should be rejected.

There is something to try for this step in the IGCSE library.

Worked example: a test plan

A test plan lists each test, the data, the type of data and the expected result.

Scenario: a program accepts the number of days for a library loan. It must be a whole number from 1 to 21.