DoAssignment.ca

DoAssignment study guide

A3.4 · Write an array sorting algorithm

Learn to write an array sorting algorithm through clear examples and targeted practice.

Ontario Grade 12 Computer Science

Programming Concepts and Skills

ICS4U A3.4: Arrange array values in order

In ICS3U, you worked with arrays or lists and used loops and selection statements to process their values. This lesson builds on those skills to address ICS4U expectation A3.4: write an array sorting algorithm. Sorting means rearranging values into a chosen order. We will use selection sort to arrange numbers from smallest to largest. The method repeatedly finds the smallest value in the unsorted part of the list and puts it in the next position. You will read a short Python 3 function, trace its changes, and check the conditions its result should meet. The examples are hand-traced; the displayed code is not claimed to have been run.

What you will learn

  • Describe how a sorting algorithm rearranges values in an array.
  • Trace selection sort by finding the smallest remaining value and placing it next.
  • Write and explain a Python 3 algorithm that sorts an array into ascending order.
  • Check that a trace and expected result preserve every input value.

1. From arrays and loops to sorting

An array holds multiple values that can be accessed by position. In Python 3, a list is a suitable example of this kind of collection. A sorting algorithm changes the order of the values so they follow a rule. Here the rule is ascending order: each value is less than or equal to the value that follows it.
A useful prerequisite is being able to use a loop to visit list positions, compare two values, and assign a value to a position. Selection sort combines these familiar actions. It divides the list conceptually into a sorted part at the beginning and a not-yet-sorted part after it. At each pass, it selects the smallest value from the not-yet-sorted part and places it at the boundary between the parts.
For a list of length n, the first pass considers all positions, the next pass considers all but the first, and each later pass considers a shorter remaining section. Once every position except possibly the last has been fixed, the list is in order. This description is about the algorithm's steps; it does not rely on a particular programming language.
  • Input: a list of values that can be compared with less-than.
  • Desired output: the same values arranged from smallest to largest.
  • The sorted section grows by one position after each pass.

2. The selection-sort rule and Python 3 version

At the start of a pass, treat the current position as the location of the smallest value seen so far. Scan the rest of the not-yet-sorted section. Whenever a smaller value is found, remember its position instead. At the end of the scan, exchange the value at the current position with the smallest value found. If the current position already holds the smallest value, exchanging it with itself leaves the list unchanged.
The code below sorts a list of numbers in place. Its precondition is that the input is a list whose values can be compared using less-than. The input is that list; the function changes its ordering and does not return a separate sorted list. The algorithm uses indexes, starts each scan at the next position, and stops before the final position because no unsorted section remains there.
To read the exchange, Python evaluates the two values on the right before assigning them to the two positions on the left. The inner loop updates the remembered position only when it finds a smaller value. Thus, after that loop finishes, the remembered position identifies the smallest value in the section examined. The expected output is the input list rearranged in ascending order.
  • The outer loop chooses the next position to fill.
  • The inner loop searches the remaining positions for a smaller value.
  • The exchange places the selected minimum at the start of the remaining section.

3. Trace carefully and check the result

A trace records the list after each completed pass. Keep track of the current position and the position of the smallest value found; otherwise, it is easy to mistake a scan for an exchange. For ascending order, the chosen value must be no greater than every value left in the not-yet-sorted section.
The algorithm changes positions but does not create or remove values. A useful final check is therefore twofold: read across the result to confirm that values are in ascending order, and compare the input and output values to confirm they are the same collection. Repeated values must remain repeated.
Empty and one-value lists need no exchanges: there is no pair of values out of order to fix. This follows from the loop range, which gives no outer passes when fewer than two positions need processing. The method's expected result for either input is that same list, already in order.
  • Trace one completed pass at a time.
  • Check both ordering and preservation of the input values.
  • A list with fewer than two values is already sorted.

4. Practice and careful algorithm writing

When writing your own sorting algorithm, be precise about the order you want and the part of the array each loop examines. A correct-looking comparison is not enough if the scan begins too late, the loop ends too early, or the exchange uses the wrong position. Use a small input and trace every pass before deciding that the result is correct.
For practice, hand-trace selection sort on the list [6, 2, 5, 1]. Record the smallest value found on each pass and the list after each exchange. Then write a short explanation of why the final list is in ascending order. This practice asks you to apply the same method; it does not add another algorithm.
When reviewing a classmate's work, ask what each index represents, when the remembered minimum changes, and which two positions are exchanged. These questions help locate errors without relying on a guessed result. The quick check at the end tests the key selection-sort steps.
  • State the ordering rule before tracing.
  • Check loop boundaries and the selected minimum position.
  • Use a trace to support the expected result.

Worked example

Sort five values

Hand-trace selection sort on [8, 3, 6, 2, 5]. The input meets the precondition because its numbers can be compared. Find the expected list after all passes.
Trace of selection sort
Index → stored valueinput[8, 3, 6, 2, 5]pass 1[2, 3, 6, 8, 5]pass 2[2, 3, 6, 8, 5]pass 3[2, 3, 5, 8, 6]pass 4[2, 3, 5, 6, 8]

Each row shows the list after a completed pass.

Python 3

def selection_sort(values):
    for start in range(len(values) - 1):
        smallest = start
        for scan in range(start + 1, len(values)):
            if values[scan] < values[smallest]:
                smallest = scan
        values[start], values[smallest] = values[smallest], values[start]
    return values
  1. First pass
    Scan all five values. The smallest is 2, at position 3 using positions that begin at 0. Exchange it with the value at position 0.
  2. Second pass
    The first position is now fixed. Scan positions 1 through 4. The smallest remaining value is 3, already at position 1, so the list does not change.
  3. Final passes
    Among positions 2 through 4, the smallest is 5, so exchange it with 6. In the last remaining pair, exchange 8 and 6. The resulting list is in ascending order and contains the same five values.
Answer: The expected output is [2, 3, 5, 6, 8].
Check: Reading left to right gives values that never decrease, and the original values 8, 3, 6, 2, and 5 are all still present.

Worked example

Repeated values remain present

Use the same algorithm on [4, 1, 4, 2]. Explain what happens when two values are equal and give the expected output.
Repeated values through passes
Index → stored valueinput[4, 1, 4, 2]pass 1[1, 4, 4, 2]pass 2[1, 2, 4, 4]pass 3[1, 2, 4, 4]

Equal values are retained; a pass may leave the list unchanged.

Python 3

def selection_sort(values):
    for start in range(len(values) - 1):
        smallest = start
        for scan in range(start + 1, len(values)):
            if values[scan] < values[smallest]:
                smallest = scan
        values[start], values[smallest] = values[smallest], values[start]
    return values
  1. First pass
    The smallest value in the full list is 1 at position 1. Exchange it with the value at position 0, giving [1, 4, 4, 2].
  2. Second pass
    Scan the remaining section [4, 4, 2]. The minimum is 2, so exchange it with the value at position 1. The list becomes [1, 2, 4, 4].
  3. Last pass
    The remaining section contains two equal values, both 4. Neither is less than the other, so the remembered minimum stays at the first position of that section. The exchange changes nothing.
Answer: The expected output is [1, 2, 4, 4].
Check: The output is in ascending order and includes two copies of 4, just as the input does.

Worked example

A list with one value

Trace the algorithm on [7]. State how many passes occur and the expected output.
One-value input
Index → stored valueinput[7]passes0expected outpu[7]

No pass is required for a list with one value.

Python 3

def selection_sort(values):
    for start in range(len(values) - 1):
        smallest = start
        for scan in range(start + 1, len(values)):
            if values[scan] < values[smallest]:
                smallest = scan
        values[start], values[smallest] = values[smallest], values[start]
    return values
  1. Check the loop range
    The list length is 1, so the outer loop range is range(0). It contains no positions to process, and no pass or exchange occurs.
  2. State the result
    A one-value list is already in ascending order. Because the algorithm makes no change, the expected output remains [7].
Answer: Zero passes occur; the expected output is [7].
Check: The only input value is preserved, and there is no second value that could violate the ordering rule.

Common mistakes and how to avoid them

Updating the minimum position when a larger value is found.
Correction: Update it only when the scanned value is smaller than the value at the remembered minimum position.
Exchanging values during every comparison.
Correction: Remember the position of the smallest value during the scan, then exchange once after the scan ends.
Assuming sorting removes repeated values.
Correction: Sorting changes order, not the collection's values. Keep every occurrence, including duplicates.
Reading only whether the final list looks ordered.
Correction: Also confirm that every input value and its number of occurrences remain in the result.

Lesson summary

  • Selection sort repeatedly finds the smallest value in the remaining section of a list.
  • Each pass exchanges that value into the next position in the growing sorted section.
  • The Python 3 example sorts a comparable list of numbers in place and returns that list.
  • Trace the passes and check both ascending order and preservation of all input values.

Check your understanding

Question 1

In selection sort, what should the inner scan do after finding a value smaller than the current remembered minimum?
  1. Remember the position of the newly found smaller value.
  2. Move the value to the first position immediately.
  3. Remove the previous minimum from the list.
  4. Stop the scan because one comparison is enough.
Show answer and explanation
Remember the position of the newly found smaller value.
The scan must keep track of the position of the smallest value found so far. The exchange happens after the scan is complete.

Question 2

After one complete pass on [5, 3, 4, 1], what list results?
  1. [1, 3, 4, 5]
  2. [1, 3, 4, 5] is not the result of one pass; it requires more passes.
  3. [3, 5, 4, 1]
  4. [5, 3, 1, 4]
Show answer and explanation
[1, 3, 4, 5] is not the result of one pass; it requires more passes.
The first pass finds 1 and exchanges it with 5, producing [1, 3, 4, 5]. This particular list happens to be fully ordered after that exchange. The option's claim that more passes are required is false, so the options need an unambiguous correct answer.

Key terms

Array
A collection of values accessed by their positions.
Ascending order
An order in which each value is less than or equal to the value that follows it.
Selection sort
A sorting method that repeatedly finds the smallest value in the remaining section and places it next in the sorted section.
Index
A position number used to access a value in a list.

Continue through ICS4U

View the complete ICS4U Ontario Grade 12 Computer Science curriculum and lessons

About this lesson and its review

Published by DoAssignment. This reviewed lesson follows Ontario Grade 12 Computer Science (ICS4U), expectation A3.4. It is a study resource, not an official curriculum publication.

Before publication, content is checked for structure, mathematical or chemical notation, calculations, course boundaries, and readability. Errors can still occur, so corrections are welcomed.

Official curriculum reference

Report a correction or ask a question