Algorithms & Flowcharts — Worked Examples

1. How to Read & Draw Flowcharts

How to Read & Draw Flowcharts

A flowchart is a picture of an algorithm. Instead of writing out every step in words, you draw boxes for the steps and arrows that show the order in which they happen. Because the shapes are standardised, anyone who knows the symbols can read your plan — and you can read theirs.

Flowcharts are drawn top to bottom. You start at the top, follow the arrows, and finish at the bottom. Each shape has a specific meaning, so the shape itself tells you what kind of step it is.

The Symbol Legend

Here are the four symbols you will use again and again. Study the shape next to each label.

Rules for a Good Flowchart

• Exactly one Start. Every flowchart begins at a single Start terminator at the top.
• Arrows show the flow. Follow the arrowheads; they always point in the direction the steps happen (normally downward).
• Decisions have exactly two labelled exits. A diamond must have one arrow labelled Yes and one labelled No — never more, never fewer, never unlabelled.
• Every path ends. No matter which branch you take, the arrows eventually reach an End terminator.
• One entry, one action. A process box does one clear step. If a box is doing several things, split it.
• No dangling arrows. Every arrow must connect two shapes; nothing floats in mid-air.

Symbol → Meaning → Example

Keep these five shapes in mind. Every flowchart in this workshop is built from nothing more than these pieces joined by arrows.

2. Pseudocode: Writing Algorithms in Plain Steps

Pseudocode: Writing Algorithms in Plain Steps

Pseudocode is a way of writing an algorithm in short, structured English. It is not any real programming language, so the computer cannot run it — but it reads almost like code, so it is the perfect bridge between an idea in your head and a program in Python. You think in pseudocode, then translate it line by line into real code.

Why pseudocode helps

• It lets you plan the logic without worrying about exact Python punctuation and spelling.
• It is easy for any human to read and check.
• Each pseudocode line usually becomes one line of real code, so translation is simple.

Common pseudocode keywords (conventions)

We indent the lines inside an IF, WHILE or FOR so it is obvious which steps belong together — exactly as Python will later force us to do.

A tiny example: greet the user by name

Problem

Ask the user for their name, then print a friendly greeting that includes it.

Pseudocode

START
  INPUT name
  SET message = "Hello, " + name
  OUTPUT message
END

In Python

name = input("What is your name? ")
message = "Hello, " + name
print(message)

Output: (if the user types Ada)

Hello, Ada

Notice how each pseudocode line turned into one Python line. That is the whole point of pseudocode: plan it in plain steps, then translate.

3. Sequential Algorithms (no decisions, no loops)

Sequential Algorithms (no decisions, no loops)

A sequential algorithm is the simplest kind: the steps run one after another, top to bottom, with no questions to answer and nothing to repeat. If you can list the steps in order, you can write a sequential algorithm. Here are three worked examples.

Example (a): Area & perimeter of a rectangle

Problem

Read the length and width of a rectangle, then calculate and display its area and perimeter.

Pseudocode

START
  INPUT length
  INPUT width
  SET area = length * width
  SET perimeter = 2 * (length + width)
  OUTPUT area
  OUTPUT perimeter
END

Trace table

Sample input: length = 5, width = 3.

In Python

length = float(input("Enter length: "))
width = float(input("Enter width: "))
area = length * width
perimeter = 2 * (length + width)
print("Area:", area)
print("Perimeter:", perimeter)

Output: (with length 5 and width 3)

Area: 15.0
Perimeter: 16.0

Example (b): Celsius → Fahrenheit converter

Problem

Read a temperature in degrees Celsius and convert it to degrees Fahrenheit using the formula F = C × 9/5 + 32.

Pseudocode

START
  INPUT celsius
  SET fahrenheit = celsius * 9 / 5 + 32
  OUTPUT fahrenheit
END

Trace table

Sample input: celsius = 100.

In Python

celsius = float(input("Enter temperature in Celsius: "))
fahrenheit = celsius * 9 / 5 + 32
print(celsius, "C =", fahrenheit, "F")

Output: (with celsius 100)

100.0 C = 212.0 F

Example (c): Swap the values of two variables

Problem

Read two values, then swap them so the first holds what the second had, and the second holds what the first had.

The trick is a temporary variable. If you just wrote a = b then b = a, the first value of a would be lost. So we park it in temp first.

Pseudocode

START
  INPUT a, b
  SET temp = a
  SET a = b
  SET b = temp
  OUTPUT a, b
END

Trace table

Sample input: a = 7, b = 4.

In Python

a = int(input("Enter a: "))
b = int(input("Enter b: "))
temp = a
a = b
b = temp
print("a =", a, "  b =", b)

Output: (with a 7 and b 4)

a = 4   b = 7

(Python also offers a one-line shortcut, a, b = b, a, but the temp version shows exactly what is happening.)

4. Making Decisions I

Making Decisions I

Real programs need to make choices. A decision asks a yes/no question and then takes one path or another. In a flowchart this is a diamond with two labelled arrows; in pseudocode and Python it is IF ... ELSE. Here are three worked examples.

Example (a): The larger of two numbers

Problem

Read two numbers and display whichever one is larger.

Pseudocode

START
  INPUT a, b
  IF a > b THEN
    OUTPUT a
  ELSE
    OUTPUT b
  END IF
END

Trace table

Sample input: a = 8, b = 5.

In Python

a = int(input("Enter a: "))
b = int(input("Enter b: "))
if a > b:
    print("The larger number is", a)
else:
    print("The larger number is", b)

Output: (with a 8 and b 5)

The larger number is 8

Example (b): Positive, negative, or zero

Problem

Read a number and report whether it is positive, negative, or zero. This needs three outcomes, so we use two decisions.

Pseudocode

START
  INPUT n
  IF n > 0 THEN
    OUTPUT "Positive"
  ELSE IF n < 0 THEN
    OUTPUT "Negative"
  ELSE
    OUTPUT "Zero"
  END IF
END

Trace table

Sample input: n = -3.

In Python

n = int(input("Enter a number: "))
if n > 0:
    print("Positive")
elif n < 0:
    print("Negative")
else:
    print("Zero")

Output: (with n -3)

Negative

Example (c): Even or odd

Problem

Read a whole number and report whether it is even or odd. A number is even when dividing it by 2 leaves no remainder. The remainder operator is mod (written % in Python).

Pseudocode

START
  INPUT n
  SET remainder = n mod 2
  IF remainder = 0 THEN
    OUTPUT "Even"
  ELSE
    OUTPUT "Odd"
  END IF
END

Trace table

Sample input: n = 7.

In Python

n = int(input("Enter a whole number: "))
remainder = n % 2
if remainder == 0:
    print(n, "is even")
else:
    print(n, "is odd")

Output: (with n 7)

7 is odd

5. Making Decisions II

Making Decisions II

Now we combine several decisions to solve richer problems. The same rule still applies: every diamond asks one yes/no question and has exactly two labelled exits. Here are three worked examples.

Example (a): Largest of three numbers

Problem

Read three numbers and display the largest. We keep a variable largest, start it at the first number, then compare it with the other two, updating it whenever we find something bigger.

Pseudocode

START
  INPUT a, b, c
  SET largest = a
  IF b > largest THEN
    SET largest = b
  END IF
  IF c > largest THEN
    SET largest = c
  END IF
  OUTPUT largest
END

Trace table

Sample input: a = 3, b = 9, c = 5.

In Python

a = int(input("Enter a: "))
b = int(input("Enter b: "))
c = int(input("Enter c: "))
largest = a
if b > largest:
    largest = b
if c > largest:
    largest = c
print("The largest is", largest)

Output: (with a 3, b 9, c 5)

The largest is 9

Example (b): Student grade calculator

Problem

Read a test score from 0 to 100 and print a letter grade: A for 90+, B for 80–89, C for 70–79, D for 60–69, otherwise F. This is a ladder of decisions checked from the top down.

Pseudocode

START
  INPUT score
  IF score >= 90 THEN
    SET grade = "A"
  ELSE IF score >= 80 THEN
    SET grade = "B"
  ELSE IF score >= 70 THEN
    SET grade = "C"
  ELSE IF score >= 60 THEN
    SET grade = "D"
  ELSE
    SET grade = "F"
  END IF
  OUTPUT grade
END

Trace table

Sample input: score = 85.

In Python

score = int(input("Enter the score (0-100): "))
if score >= 90:
    grade = "A"
elif score >= 80:
    grade = "B"
elif score >= 70:
    grade = "C"
elif score >= 60:
    grade = "D"
else:
    grade = "F"
print("Grade:", grade)

Output: (with score 85)

Grade: B

Example (c): Leap-year check

Problem

Read a year and decide whether it is a leap year. The rule: a year is a leap year if it is divisible by 4, except that years divisible by 100 are not leap years — unless they are also divisible by 400 (then they are).

Pseudocode

START
  INPUT year
  IF year mod 4 = 0 THEN
    IF year mod 100 = 0 THEN
      IF year mod 400 = 0 THEN
        OUTPUT "Leap year"
      ELSE
        OUTPUT "Not a leap year"
      END IF
    ELSE
      OUTPUT "Leap year"
    END IF
  ELSE
    OUTPUT "Not a leap year"
  END IF
END

Trace table

Sample input: year = 2000.

In Python

year = int(input("Enter a year: "))
if year % 4 == 0:
    if year % 100 == 0:
        if year % 400 == 0:
            print(year, "is a leap year")
        else:
            print(year, "is not a leap year")
    else:
        print(year, "is a leap year")
else:
    print(year, "is not a leap year")

Output: (with year 2000)

2000 is a leap year

Experienced programmers often fold this into one line — if year % 4 == 0 and (year % 100 != 0 or year % 400 == 0): — but the nested version matches the flowchart step by step, which makes the rule easier to learn.

6. Counting & Accumulating with Loops

Counting & Accumulating with Loops

Many programs work by repeating a small step many times while keeping a running number that grows as they go. That running number is called an accumulator (for adding up) or a counter (for counting). In this chapter we build four classic examples. For every one you will see a flowchart, pseudocode, a hand trace table, and real Python so you can run it yourself.

The key idea to watch in each trace table is the accumulator column: how the running total changes on every single pass through the loop.

Example (a): Sum of the numbers 1 to N

Problem

Ask the user for a whole number N and add up every number from 1 up to N (so if N is 5 the answer is 1+2+3+4+5 = 15).

Pseudocode

INPUT N
SET total = 0
SET i = 1
WHILE i <= N
    SET total = total + i
    SET i = i + 1
OUTPUT total

Trace table

Sample input: N = 5. One row per loop iteration. Watch the total (accumulator) column grow.

The loop stops when i becomes 6 (because 6 <= 5 is No), and we output 15.

In Python

N = 5
total = 0
i = 1
while i <= N:
    total = total + i
    i = i + 1
print(total)

# Output:
# 15

Example (b): Factorial of N

Problem

The factorial of N (written N!) multiplies every whole number from 1 up to N. For example 4! = 1 x 2 x 3 x 4 = 24.

Pseudocode

INPUT N
SET fact = 1
SET i = 1
WHILE i <= N
    SET fact = fact * i
    SET i = i + 1
OUTPUT fact

Trace table

Sample input: N = 4. The accumulator is fact, and it starts at 1 (not 0, because multiplying by 0 would wipe everything out).

Answer: 24.

In Python

N = 4
fact = 1
i = 1
while i <= N:
    fact = fact * i
    i = i + 1
print(fact)

# Output:
# 24

Example (c): Multiplication table of N (1 to 10)

Problem

Print the multiplication table of N from N x 1 up to N x 10.

Pseudocode

INPUT N
FOR i FROM 1 TO 10
    SET product = N * i
    OUTPUT N, "x", i, "=", product

Trace table

Sample input: N = 7. One row per iteration; the product column is what gets printed each time.

In Python

N = 7
for i in range(1, 11):
    product = N * i
    print(N, "x", i, "=", product)

# Output:
# 7 x 1 = 7
# 7 x 2 = 14
# 7 x 3 = 21
# 7 x 4 = 28
# 7 x 5 = 35
# 7 x 6 = 42
# 7 x 7 = 49
# 7 x 8 = 56
# 7 x 9 = 63
# 7 x 10 = 70

Example (d): Average of N entered numbers

Problem

Ask how many numbers (N) the user will enter, read them one by one, add them into a running total, then divide the total by N to get the average.

Pseudocode

INPUT N
SET total = 0
SET count = 1
WHILE count <= N
    INPUT num
    SET total = total + num
    SET count = count + 1
SET avg = total / N
OUTPUT avg

Trace table

Sample input: N = 4, and the four numbers entered are 10, 20, 30, 40. Watch the total accumulator.

Average = 100 / 4 = 25.0.

In Python

N = 4
numbers = [10, 20, 30, 40]   # pretend these were typed in one by one
total = 0
count = 1
while count <= N:
    num = numbers[count - 1]
    total = total + num
    count = count + 1
avg = total / N
print(avg)

# Output:
# 25.0

7. Number-Crunching Algorithms

Number-Crunching Algorithms

These algorithms take an integer apart one digit at a time. Two tiny operations do almost all the work, so learn them cold:

• n % 10 (remainder when dividing by 10) gives the last digit. Example: 1234 % 10 = 4.
• n // 10 (whole-number division by 10) chops off the last digit. Example: 1234 // 10 = 123.

Repeating "grab last digit, then chop it off" peels a number down to nothing. Every trace table below has a % 10 column and a // 10 column so you can see each digit fall off.

Example (a): Count the digits in an integer

Problem

Read a non-negative integer and count how many digits it has (for example 4705 has 4 digits).

Pseudocode

INPUT n
SET count = 0
WHILE n > 0
    SET count = count + 1
    SET n = n // 10
OUTPUT count

Trace table

Sample input: n = 4705. Each iteration chops one digit off with // 10.

Digit count: 4.

In Python

n = 4705
count = 0
while n > 0:
    count = count + 1
    n = n // 10
print(count)

# Output:
# 4

Example (b): Sum of the digits of an integer

Problem

Add together all the digits of an integer (for 4705 that is 4+7+0+5 = 16).

Pseudocode

INPUT n
SET sum = 0
WHILE n > 0
    SET digit = n % 10
    SET sum = sum + digit
    SET n = n // 10
OUTPUT sum

Trace table

Sample input: n = 4705. The sum column is the accumulator.

Digit sum: 16.

In Python

n = 4705
total = 0
while n > 0:
    digit = n % 10
    total = total + digit
    n = n // 10
print(total)

# Output:
# 16

Example (c): Reverse an integer

Problem

Turn an integer back to front, so 1234 becomes 4321.

The trick: peel the last digit off the input with % 10, and push it onto a growing answer by doing rev = rev * 10 + digit. Multiplying rev by 10 shifts its digits left to make room for the new one.

Pseudocode

INPUT n
SET rev = 0
WHILE n > 0
    SET digit = n % 10
    SET rev = rev * 10 + digit
    SET n = n // 10
OUTPUT rev

Trace table

Sample input: n = 1234.

Reversed number: 4321.

In Python

n = 1234
rev = 0
while n > 0:
    digit = n % 10
    rev = rev * 10 + digit
    n = n // 10
print(rev)

# Output:
# 4321

Example (d): Check if a number is a palindrome

Problem

A palindrome reads the same forwards and backwards (like 1221 or racecar). Decide whether an integer is a palindrome by reversing it and comparing with the original.

Pseudocode

INPUT n
SET original = n
SET rev = 0
WHILE n > 0
    SET rev = rev * 10 + (n % 10)
    SET n = n // 10
IF rev == original
    OUTPUT "palindrome"
ELSE
    OUTPUT "not a palindrome"

Trace table

Sample input: n = 1221 (we save original = 1221 first).

Final check: rev (1221) == original (1221) is Yes, so 1221 is a palindrome.

In Python

n = 1221
original = n
rev = 0
while n > 0:
    rev = rev * 10 + (n % 10)
    n = n // 10
if rev == original:
    print("palindrome")
else:
    print("not a palindrome")

# Output:
# palindrome

8. Classic Math Algorithms

Classic Math Algorithms

These four algorithms show up again and again in programming courses and interviews. Each uses a loop with a clear changing state, so trace tables are the best way to understand them.

Example (a): Check if a number is prime

Problem

A prime number (2, 3, 5, 7, 11, ...) has exactly two divisors: 1 and itself. Decide whether N is prime by testing every possible divisor from 2 up to N-1: if any divides N evenly, N is not prime.

Reading the chart: the inner diamond asks "does i divide N?". If Yes we set isPrime = false and leave the loop; if No we add 1 to i and check the next divisor. When i passes N-1 with isPrime still true, N is prime.

Pseudocode

INPUT N
SET isPrime = true
SET i = 2
WHILE i <= N - 1
    IF N % i == 0
        SET isPrime = false
    SET i = i + 1
IF isPrime == true
    OUTPUT "prime"
ELSE
    OUTPUT "not prime"

Trace table

Sample input: N = 7. We test i = 2, 3, 4, 5, 6. None divide 7 evenly, so the remainder (N % i) is never 0 and isPrime stays true.

isPrime is still true, so 7 is prime. (If we had tried N = 9, then at i = 3 the remainder 9 % 3 would be 0, isPrime would flip to false, and 9 would be "not prime".)

In Python

N = 7
is_prime = True
i = 2
while i <= N - 1:
    if N % i == 0:
        is_prime = False
    i = i + 1
if is_prime and N >= 2:
    print("prime")
else:
    print("not prime")

# Output:
# prime

Example (b): Greatest common divisor (Euclid's algorithm)

Problem

The greatest common divisor (GCD) of two numbers is the largest number that divides both. Euclid's algorithm finds it fast: keep replacing the pair (a, b) with (b, a % b) until b becomes 0; then a is the answer.

Pseudocode

INPUT a, b
WHILE b != 0
    SET temp = a % b
    SET a = b
    SET b = temp
OUTPUT a

Trace table

Sample input: a = 48, b = 36. Watch both a and b each step.

When b reaches 0 the loop stops and a = 12 is the GCD of 48 and 36.

In Python

a = 48
b = 36
while b != 0:
    temp = a % b
    a = b
    b = temp
print(a)

# Output:
# 12

Example (c): First N Fibonacci numbers

Problem

The Fibonacci sequence starts 0, 1 and every later number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, ... Print the first N of them.

Pseudocode

INPUT N
SET prev = 0
SET curr = 1
FOR i FROM 1 TO N
    OUTPUT prev
    SET next = prev + curr
    SET prev = curr
    SET curr = next

Trace table

Sample input: N = 7. The printed number each pass is the prev value.

Numbers printed: 0 1 1 2 3 5 8.

In Python

N = 7
prev = 0
curr = 1
for i in range(N):
    print(prev, end=" ")
    next_num = prev + curr
    prev = curr
    curr = next_num
print()

# Output:
# 0 1 1 2 3 5 8

Example (d): Compute x raised to the power n with a loop

Problem

Work out x to the power n (x multiplied by itself n times) without using a built-in power operator. For example 2 to the power 5 is 2 x 2 x 2 x 2 x 2 = 32.

Pseudocode

INPUT x, n
SET result = 1
SET i = 1
WHILE i <= n
    SET result = result * x
    SET i = i + 1
OUTPUT result

Trace table

Sample input: x = 2, n = 5. The accumulator result starts at 1 and gets multiplied by x each pass.

2 to the power 5 = 32.

In Python

x = 2
n = 5
result = 1
i = 1
while i <= n:
    result = result * x
    i = i + 1
print(result)

# Output:
# 32

9. Searching

Searching

Searching means looking for a target value inside a list. The two methods below are the foundation of a huge amount of computer science. The big lesson: a smarter method (binary search) can be dramatically faster, but it has a requirement (the list must be sorted).

Example (a): Linear search

Problem

Walk through a list one item at a time from the front. If you find the target, report its position; if you reach the end without finding it, report "not found".

Pseudocode

INPUT list, target
SET index = 0
WHILE index < length(list)
    IF list[index] == target
        OUTPUT "found at", index
        STOP
    SET index = index + 1
OUTPUT "not found"

Trace table

Sample: list = [4, 8, 15, 16, 23, 42], target = 16.

Target 16 is found at index 3 after checking 4 items.

In Python

numbers = [4, 8, 15, 16, 23, 42]
target = 16
found_at = -1
index = 0
while index < len(numbers):
    if numbers[index] == target:
        found_at = index
        break
    index = index + 1
if found_at != -1:
    print("found at index", found_at)
else:
    print("not found")

# Output:
# found at index 3

Example (b): Binary search (sorted list)

Problem

Find a target in a list that is already sorted in order. Instead of checking items one by one, jump to the middle and throw away half the list each step.

The "guess the number" analogy. A friend thinks of a number between 1 and 100 and you must guess it; after each guess they say "higher" or "lower". The smart move is never to guess 1, 2, 3, ... in order. You guess 50 (the middle). If they say "higher" you now know it is 51-100, so you guess 75; if "lower" it is 1-49, so you guess 25. Each guess cuts the range in half, so you always win in about 7 guesses, not 100. Binary search is exactly that strategy on a sorted list. It keeps two markers, low and high, that fence in the part still worth searching, and checks the mid point between them.

Pseudocode

INPUT sortedList, target
SET low = 0
SET high = length(sortedList) - 1
WHILE low <= high
    SET mid = (low + high) // 2
    IF sortedList[mid] == target
        OUTPUT "found at", mid
        STOP
    IF sortedList[mid] < target
        SET low = mid + 1
    ELSE
        SET high = mid - 1
OUTPUT "not found"

Trace table

Sample: sorted list (10 items, index 0-9) = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], target = 23. Each row halves the range using low, high and mid.

Binary search found 23 at index 5 in just 3 comparisons. A linear search of the same list would have needed 6 comparisons to reach index 5.

In Python

sorted_list = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
low = 0
high = len(sorted_list) - 1
found_at = -1
while low <= high:
    mid = (low + high) // 2
    if sorted_list[mid] == target:
        found_at = mid
        break
    if sorted_list[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
if found_at != -1:
    print("found at index", found_at)
else:
    print("not found")

# Output:
# found at index 5

How fast? Linear vs binary as the list grows

Linear search may have to look at every item, so in the worst case it takes as many steps as there are items. Binary search halves the list each step, so its worst case is roughly how many times you can halve the number before reaching 1 (that is log base 2). The difference becomes enormous for big lists.

Searching a million sorted items takes binary search only about 20 checks instead of a million. The trade-off: binary search needs the list to be sorted first, while linear search works on any list in any order.

10. Sorting: Putting Things in Order

Why order matters

Sorting means rearranging a list so its items follow a rule — usually smallest–to–largest (ascending) or largest–to–smallest (descending). It feels simple, but it is one of the most useful things a computer does, because sorted data unlocks faster algorithms.

• Binary search only works on a sorted list. On a sorted list of a million items you can find any value in about 20 comparisons; on an unsorted list you may need a million.
• Finding duplicates, the median, or the top 10 all become easy once items sit next to their neighbours.
• People read sorted data faster — a phone book, a leaderboard, search results.

Below we learn three classic sorts. To make them easy to compare, every example sorts the same list into ascending order: [5, 2, 4, 1, 3]. Watch how each method reaches the same answer [1, 2, 3, 4, 5] by a different route.

(a) Bubble Sort

Bubble sort repeatedly walks through the list, comparing each pair of neighbours and swapping them if they are in the wrong order. After each full pass the largest remaining value "bubbles" to the end.

Problem

Sort the list [5, 2, 4, 1, 3] into ascending order using bubble sort.

Pseudocode

BUBBLE_SORT(a):
    swapped = True
    WHILE swapped:
        swapped = False
        FOR i FROM 0 TO length(a) - 2:
            IF a[i] > a[i+1]:
                swap a[i] and a[i+1]
                swapped = True
    RETURN a

Trace table

The array state after each complete pass over [5, 2, 4, 1, 3]:

In Python

def bubble_sort(a):
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(a) - 1):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
    return a

print(bubble_sort([5, 2, 4, 1, 3]))

Output:

[1, 2, 3, 4, 5]

(b) Selection Sort

Selection sort builds the sorted list one slot at a time. On each pass it scans the unsorted part, finds the smallest remaining value, and swaps it into the next position from the front.

Problem

Sort [5, 2, 4, 1, 3] into ascending order using selection sort.

Pseudocode

SELECTION_SORT(a):
    FOR i FROM 0 TO length(a) - 2:
        min = i
        FOR j FROM i+1 TO length(a) - 1:
            IF a[j] < a[min]:
                min = j
        swap a[i] and a[min]
    RETURN a

Trace table

The array state after each pass places one more value in its final position (shown in bold conceptually at the front):

In Python

def selection_sort(a):
    for i in range(len(a) - 1):
        smallest = i
        for j in range(i + 1, len(a)):
            if a[j] < a[smallest]:
                smallest = j
        a[i], a[smallest] = a[smallest], a[i]
    return a

print(selection_sort([5, 2, 4, 1, 3]))

Output:

[1, 2, 3, 4, 5]

(c) Insertion Sort

Insertion sort grows a sorted region on the left. It takes the next item and slides it leftward past any larger items until it drops into the right place — exactly how many people sort a hand of playing cards.

Problem

Sort [5, 2, 4, 1, 3] into ascending order using insertion sort.

Pseudocode

INSERTION_SORT(a):
    FOR i FROM 1 TO length(a) - 1:
        key = a[i]
        j = i - 1
        WHILE j >= 0 AND a[j] > key:
            a[j+1] = a[j]
            j = j - 1
        a[j+1] = key
    RETURN a

Trace table

After inserting each new key into the sorted left region of [5, 2, 4, 1, 3]:

In Python

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

print(insertion_sort([5, 2, 4, 1, 3]))

Output:

[1, 2, 3, 4, 5]

Compare the three: all three turn [5, 2, 4, 1, 3] into [1, 2, 3, 4, 5]. Bubble sort swaps neighbours many times, selection sort makes few swaps but always scans the rest, and insertion sort does little work when the data is already nearly sorted.

11. Working with Lists & Arrays

Scanning a list

A huge number of real programs boil down to one idea: walk through a list once, remembering something as you go. The "something you remember" might be the biggest value seen so far, the smallest, a running count, or the best two values. The pattern is always the same — start with a sensible first guess, then update it whenever you find something better. Every example below uses the sample list [4, 9, 2, 9, 7].

(a) Find the maximum (and its position)

Problem

Given a list of numbers, find the largest value and the index where it first appears.

Pseudocode

FIND_MAX(a):
    best = a[0]
    pos  = 0
    FOR i FROM 1 TO length(a) - 1:
        IF a[i] > best:
            best = a[i]
            pos  = i
    OUTPUT best, pos

Trace table

In Python

def find_max(a):
    best, pos = a[0], 0
    for i in range(1, len(a)):
        if a[i] > best:
            best, pos = a[i], i
    return best, pos

print(find_max([4, 9, 2, 9, 7]))

Output:

(9, 1)

(b) Find the minimum

Problem

Find the smallest value in a list of numbers.

Pseudocode

FIND_MIN(a):
    low = a[0]
    FOR i FROM 1 TO length(a) - 1:
        IF a[i] < low:
            low = a[i]
    OUTPUT low

Trace table

In Python

def find_min(a):
    low = a[0]
    for i in range(1, len(a)):
        if a[i] < low:
            low = a[i]
    return low

print(find_min([4, 9, 2, 9, 7]))

Output:

2

(c) Count how many times a value occurs

Problem

Count how many times a target value (here, 9) appears in the list.

Pseudocode

COUNT(a, target):
    count = 0
    FOR i FROM 0 TO length(a) - 1:
        IF a[i] == target:
            count = count + 1
    OUTPUT count

Trace table

Counting occurrences of 9 in [4, 9, 2, 9, 7]:

In Python

def count_value(a, target):
    count = 0
    for x in a:
        if x == target:
            count += 1
    return count

print(count_value([4, 9, 2, 9, 7], 9))

Output:

2

(d) Find the second-largest value

Problem

Find the second-largest value in a list by tracking the two best values seen so far.

Pseudocode

SECOND_LARGEST(a):
    best   = -infinity
    second = -infinity
    FOR each x IN a:
        IF x > best:
            second = best
            best   = x
        ELSE IF x > second AND x < best:
            second = x
    OUTPUT second

Trace table

Scanning [4, 9, 2, 9, 7]. (Note the duplicate 9 is not greater than best, so it is skipped — the second-largest distinct value is 7.)

In Python

def second_largest(a):
    best = second = float("-inf")
    for x in a:
        if x > best:
            second, best = best, x
        elif second < x < best:
            second = x
    return second

print(second_largest([4, 9, 2, 9, 7]))

Output:

7

12. Everyday Flowcharts: Algorithms in Real Life

Algorithms you already follow

You run algorithms every day without calling them that: using an ATM, logging in, buying a snack, crossing at the lights. Each is a sequence of steps with decisions (branches) and sometimes loops (repeating until something is true). Drawing them as flowcharts makes the hidden logic — especially the "what if it goes wrong?" branches — visible. Watch the Yes/No labels: getting a branch backwards is the most common bug.

(a) ATM cash withdrawal

Problem

A customer inserts a card and asks for cash. The machine must check the PIN, check the balance, and only then dispense money.

Pseudocode

ATM_WITHDRAW:
    pin = INPUT
    IF pin is not valid:
        show "Incorrect PIN"
    ELSE:
        amount = INPUT
        IF amount <= balance:
            dispense(amount)
            balance = balance - amount
            print receipt
        ELSE:
            show "Insufficient funds"

In Python

def atm_withdraw(entered_pin, correct_pin, amount, balance):
    if entered_pin != correct_pin:
        return "Incorrect PIN", balance
    if amount > balance:
        return "Insufficient funds", balance
    balance -= amount
    return f"Dispensed {amount}", balance

print(atm_withdraw("1234", "1234", 60, 200))

Output:

('Dispensed 60', 140)

(b) Website login with a maximum of 3 attempts

Problem

Let a user try to log in. Allow at most three wrong passwords, then lock the account.

Pseudocode

LOGIN:
    tries = 0
    WHILE tries < 3:
        pw = INPUT
        IF pw is correct:
            grant access
            STOP
        ELSE:
            tries = tries + 1
    lock account

Trace table

User types "abc", "xyz", then the correct "pass" on the third try:

In Python

def login(attempts, correct="pass"):
    tries = 0
    while tries < 3:
        pw = attempts[tries]
        if pw == correct:
            return "Access granted"
        tries += 1
    return "Account locked"

print(login(["abc", "xyz", "pass"]))
print(login(["a", "b", "c"]))

Output:

Access granted
Account locked

(c) Vending machine

Problem

A customer selects an item, inserts money a coin at a time, and the machine either gives the item plus change, or refunds if they cancel.

Pseudocode

VENDING_MACHINE:
    price = selected item price
    paid  = 0
    WHILE paid < price:
        coin = INPUT          ' a coin, or "cancel"
        IF coin == "cancel":
            refund(paid)
            STOP
        paid = paid + coin
    dispense item
    IF paid > price:
        give change (paid - price)

In Python

def vend(price, coins):
    paid = 0
    for coin in coins:
        if coin == "cancel":
            return f"Refund {paid}"
        paid += coin
        if paid >= price:
            return f"Dispense item, change {paid - price}"
    return f"Refund {paid}"   # ran out of coins

print(vend(75, [25, 25, 25]))
print(vend(75, [25, "cancel"]))

Output:

Dispense item, change 0
Refund 25

(d) Traffic-light controller cycle

Problem

Control a traffic light that repeats forever: Green, then Amber, then Red, each for a fixed time, then back to Green.

Pseudocode

TRAFFIC_LIGHT:
    REPEAT:
        set light GREEN;  wait 30s
        set light AMBER;  wait 5s
        set light RED;    wait 30s
    UNTIL power is off

In Python

def traffic_cycle(cycles):
    sequence = [("GREEN", 30), ("AMBER", 5), ("RED", 30)]
    log = []
    for _ in range(cycles):          # 'cycles' stands in for "while powered on"
        for colour, seconds in sequence:
            log.append(f"{colour} {seconds}s")
    return log

for step in traffic_cycle(2):
    print(step)

Output:

GREEN 30s
AMBER 5s
RED 30s
GREEN 30s
AMBER 5s
RED 30s

13. From Flowchart to Code: The Bridge

The one skill that ties it all together

A flowchart shows what should happen; code tells the computer how. Once you see that every flowchart shape maps to a small, predictable piece of Python, translation stops being mysterious. This chapter makes that mapping explicit and then walks a single problem all the way across the bridge.

Symbol / construct → Python mapping

Worked example: sum of even numbers from 1 to N

Problem

Read a number N, then add up every even number from 1 to N and print the total. For N = 6 the even numbers are 2, 4, 6, so the answer is 12.

Pseudocode

SUM_EVENS:
    N = INPUT
    total = 0
    i = 1
    WHILE i <= N:
        IF i is even:
            total = total + i
        i = i + 1
    OUTPUT total

Trace table

Tracing with N = 6:

In Python

Notice how each flowchart shape became one line, following the mapping table above:

def sum_evens(n):
    total = 0            # process box
    i = 1                # process box
    while i <= n:        # loop-back arrow
        if i % 2 == 0:   # decision diamond
            total += i   # process box
        i += 1           # process box
    return total         # terminator

N = 6                    # stands in for input()
print(sum_evens(N))

Output:

12

Practice challenges

Now try the whole bridge yourself. For each problem below, draw a flowchart, write pseudocode, build a trace table on a sample input, then code it in Python:

1. Read a number and print whether it is odd or even.
2. Read 5 numbers and print their average.
3. Print the multiplication table (1 to 12) for a number the user chooses.
4. Read a number N and print its factorial (N! = 1×2×…×N).
5. Count how many vowels are in a word the user types.
6. Decide whether a given year is a leap year.
7. Read a list of marks and print how many are a pass (≥ 40) and how many fail.
8. Check whether a short word is a palindrome (reads the same backwards).