DoAssignment study guide

C2.3 · Compare sorting algorithm costs

Learn to compare sorting algorithm costs through clear examples and targeted practice.

Ontario Grade 12 Computer Science

Designing Modular Programs

A Grade 12 lesson for ICS4U expectation C2.3

Sorting rearranges values into a chosen order. With ICS3U experience using lists, loops, and comparisons, you can trace how a sorting algorithm works and count its operations. This lesson compares selection sort, insertion sort, and a basic bubble sort. It considers key comparisons and movements separately, then connects the patterns to input size. The examples use distinct integers in ascending order as the required output. The code and traces are for study; they are not claims that code was executed.

What you will learn

Compare sorting algorithms by counting key comparisons and data movements.
Describe how comparison counts change as input size grows for selection, insertion, and basic bubble sort.
Use the same input and counting rules to make a fair comparison.
Limit conclusions to the algorithm versions and inputs that were examined.

1. Review: input, output, and counting rules

A sorting algorithm receives a list and rearranges its values. In this lesson, each input is a list of distinct integers, and the expected output has the same values in ascending order. A useful comparison begins by naming the input and the required output.

A key comparison checks two values to decide their relative order. A swap exchanges values at two positions. A shift moves a value to another position, usually to make room for a value being inserted. These are different kinds of work, so report them separately. Do not count loop checks or index checks as key comparisons in the examples.

To compare algorithms fairly, trace the same input and use the same counting conventions. The number of operations in one trace is evidence about that run. It is not a timing measurement, and it does not by itself prove that one method is always better.

State the input and required output.
Count key comparisons separately from swaps and shifts.
Use consistent counting rules for each method.

2. Three methods and how their costs grow

Selection sort finds the smallest value in the portion not yet sorted and places it at the next position. On a list of length n, its passes compare the candidate with the other remaining values: n−1 comparisons on the first pass, then n−2, continuing down to 1. Thus its comparison count is the same for every input order of that length. It makes at most n−1 swaps if it swaps only when the selected value is not already in place.

Insertion sort grows a sorted portion from left to right. It takes the next value and compares it with values in that portion, shifting larger values right until it finds where the new value belongs. On an already ascending input, it makes one key comparison for each value after the first and no shifts. On a reverse-ordered input, each new value passes all previously sorted values. Its comparison and shift counts therefore depend on input order.

Basic bubble sort compares adjacent values and swaps a pair when it is out of order. In the version used here, it completes every pass, with one fewer adjacent comparison on each later pass. Its comparison count is the same for all inputs of a given length, while its swap count depends on how values are arranged.

For selection sort and this basic bubble sort, the comparison total is 1 + 2 + … + (n−1), which equals n(n−1)/2. As n grows, these totals grow roughly in proportion to n squared: doubling n makes the count roughly four times as large for large n. This is a description of the stated versions and their comparison counts, not a claim about every sorting method. Insertion sort ranges from n−1 comparisons on already sorted input to n(n−1)/2 on reverse-ordered input. The input order helps explain why its costs vary.

1+2+\cdots +(n-1)=\frac{n(n-1)}{2}

Selection and basic bubble sort use n(n−1)/2 key comparisons for a list of length n.
Insertion sort's comparison and shift counts depend on input order.
Selection-sort swaps and bubble-sort swaps are distinct from their comparison totals.

3. Read and trace a short program

This Python 3 example shows insertion sort. Its precondition is that values is a list of comparable, distinct integers. The input is the list supplied by the caller; the function rearranges that list and returns it in ascending order. For a cost trace, count a comparison only when two list values are compared. Count each rightward movement of an existing value as one shift.

For each position after the first, the algorithm saves that value as item. It checks earlier values from right to left. While an earlier value is larger, it shifts that value one position right. It then puts item in the space left for it. Each completed pass leaves the portion up to that position sorted. The expected output for input [3, 1, 4, 2] is [1, 2, 3, 4].

The first value starts the sorted portion.
Larger earlier values shift right to make room.
The code describes an algorithm; operation counts below come from hand traces.

4. Interpreting comparisons as input size grows

For selection sort, each new input value increases the pass counts in a predictable way: the total comparison count for length n is n(n−1)/2. The same pattern applies to the basic bubble-sort version here. For example, length 5 gives 10 comparisons, while length 10 gives 45. These are calculated from the formula, not measured computer timings.

For insertion sort, input order changes the trace. On an already ascending list of length n, there is one comparison for each of the n−1 values after the first and no shifts. On reverse-ordered input, the successive insertions compare against and shift all values already in the sorted portion, giving the same triangular total n(n−1)/2 for both comparisons and shifts under the stated convention.

When you compare costs, describe both the pattern and its conditions. A useful statement is that selection sort makes the same number of key comparisons for any input order of a fixed length, whereas insertion sort can make many fewer comparisons and shifts when values are already in order. Do not turn that into a claim that one algorithm is always faster: this lesson compares selected operation counts, not every possible cost.

A cost pattern describes how operation counts change with input size.
Input order can change insertion-sort work even when list length stays the same.
Explain the scope of a comparison rather than claiming a universal winner.

Cost patterns for the versions studied

Algorithm	Key-comparison pattern	Movement pattern
Selection sort	n(n−1)/2 for any input order	At most n−1 swaps with no self-swaps
Insertion sort	n−1 on ascending input; n(n−1)/2 on reverse input	0 shifts on ascending input; n(n−1)/2 on reverse input
Basic bubble sort	n(n−1)/2 for any input order when all passes complete	Swaps depend on input order

Worked example

Already ascending input

Compare selection sort and insertion sort on [1, 2, 3, 4, 5]. Count key comparisons, selection-sort swaps, and insertion-sort shifts. Use selection sort with no swap when the selected minimum is already in place. State the expected output. Do not count loop or index checks.

Counts for ascending input

Calculated by hand for [1, 2, 3, 4, 5]. Comparison and movement counts are shown as separate labelled cells.

Python 3

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

Count selection comparisons
There are four passes. The remaining portions require 4, 3, 2, and 1 comparisons. The smallest value is already at the start of each portion, so under the no-self-swap convention no swap occurs.
$4+3+2+1=10$
Count insertion work
Each of the four values after the first is compared once with the preceding value. Each is already larger, so none of the earlier values shifts.
$4\text{ comparisons},\quad 0\text{ shifts}$
State the result
Both methods leave the values in ascending order. On this particular input, insertion sort uses fewer key comparisons.

Answer: Both produce [1, 2, 3, 4, 5]. Selection sort uses 10 key comparisons and 0 swaps. Insertion sort uses 4 key comparisons and 0 shifts.

Check: The selection-sort swap count follows the stated rule: it skips a swap when the minimum is already in place. The comparison counts describe this exact five-value input.

Worked example

Reverse order and insertion sort

Trace insertion sort on [5, 4, 3, 2, 1]. Count comparisons between list values and shifts of existing values. Do not count index checks. State the expected output.

Insertion-sort work by insertion

Each row records calculated counts for the next value inserted into [5, 4, 3, 2, 1].

Python 3

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

Insert 4, then 3
For 4, compare with 5 and shift 5 once. For 3, compare with 5 and 4 and shift both. The sorted portion grows after each insertion. 1+2=3 comparisons and 3 shifts
Insert 2
The value 2 is compared with 5, 4, and 3. All three are larger, so each shifts right before 2 is placed.
$3\text{ comparisons},\quad 3\text{ shifts}$
Insert 1 and total
The value 1 is compared with all four values in the sorted portion, and all four shift right. Adding the four insertions gives equal totals for comparisons and shifts.
$1+2+3+4=10$

Answer: The expected output is [1, 2, 3, 4, 5]. Insertion sort uses 10 key comparisons and 10 shifts.

Check: The reverse order makes each inserted value smaller than every value already in the sorted portion. This explains the larger count than in the ascending-input example.

Worked example

Compare three methods on one input

Compare selection sort, insertion sort, and basic bubble sort on [3, 1, 4, 2]. Count key comparisons for all three. Count swaps for selection and bubble sort, and shifts for insertion sort. Bubble sort completes each pass, shortening the compared portion by one each time. State the common expected output.

Operation counts for [3, 1, 4, 2]

Counts are hand-traced under the conventions stated in the problem; movements retain their distinct labels.

Pseudocode

BUBBLE-SORT(values)
    for end from length(values) - 1 down to 1
        for i from 0 to end - 1
            if values[i] > values[i + 1]
                swap values[i] and values[i + 1]
    return values

Trace selection sort
The passes compare 3, 2, and 1 pairs of values. The minimum is placed by swapping 3 with 1, then 3 with 2, then 4 with 3. No pass selects a minimum already in place.
$3+2+1=6\text{ comparisons},\quad 3\text{ swaps}$
Trace insertion sort
Insert 1 by comparing with 3 and shifting 3. Insert 4 with one comparison and no shift. Insert 2 by comparing with 4 and then 3, shifting both. The sorted output is [1, 2, 3, 4].
$1+1+2=4\text{ comparisons},\quad 1+0+2=3\text{ shifts}$
Trace basic bubble sort
The three complete passes compare 3, 2, and 1 adjacent pairs. Swaps occur for 3 with 1, 4 with 2, and 3 with 2. The counts are therefore six comparisons and three swaps.
$3+2+1=6\text{ comparisons},\quad 3\text{ swaps}$

Answer: All three produce [1, 2, 3, 4]. Selection sort uses 6 comparisons and 3 swaps; insertion sort uses 4 comparisons and 3 shifts; basic bubble sort uses 6 comparisons and 3 swaps.

Check: Insertion sort has the fewest key comparisons in this trace. The result supports no broader claim about every input or every version of these methods.

Common mistakes and how to avoid them

Combining comparisons, swaps, and shifts into one operation total.

Correction: Report each type separately because they describe different actions.

Saying selection sort compares n values on every pass.

Correction: A pass with k remaining values compares the candidate with the other k−1 values.

Counting a selection-sort swap when the selected minimum is already in place.

Correction: With the convention used here, swap only when the selected value is at a different position.

Claiming one algorithm is always best based on one short trace.

Correction: State the input, algorithm version, and counted operations; limit the conclusion to that evidence.

Lesson summary

Sorting costs can be compared by counting key comparisons and data movements separately.
Selection sort and basic bubble sort use n(n−1)/2 comparisons in the versions studied; their movements are counted separately.
Insertion sort's comparisons and shifts depend on input order, ranging from low counts on ascending input to triangular totals on reverse input.
A fair comparison uses the same input and counting rules, and a careful conclusion states what the evidence does and does not show.

Check your understanding

Question 1

How many key comparisons does selection sort make on a list of length 6?

Show answer and explanation

The passes compare 5, 4, 3, 2, and 1 values against the current candidate, for a total of 15.

Question 2

For the insertion-sort version taught here, what happens on an already ascending list?

It makes no key comparisons and shifts every value.
It makes one key comparison per value after the first and no shifts.
It makes n(n−1)/2 shifts.
It reverses the list before sorting.

Show answer and explanation

It makes one key comparison per value after the first and no shifts.

Each new value is compared with its predecessor and is already in the correct place, so no earlier value needs to shift.

Question 3

A trace on one input shows fewer comparisons for insertion sort than for bubble sort. What conclusion is justified?

Insertion sort always makes fewer comparisons.
Bubble sort cannot sort that input.
Insertion sort made fewer comparisons on that input under the stated rules.
Insertion sort must be faster on every computer.

Show answer and explanation

Insertion sort made fewer comparisons on that input under the stated rules.

One trace supports a conclusion about its particular input and counting rules, not a universal ranking.

Key terms

Key comparison: A check of the relative order of two values being sorted.
Swap: An exchange of the values at two list positions.
Shift: Moving a value to another position to make room for an inserted value.
Input order: The arrangement of values in a list before sorting begins.

Continue through ICS4U

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

Tutor support for C2.3 · Compare sorting algorithm costs

Working on C2.3 · Compare sorting algorithm costs in ICS4U? Bring the question and your own attempt. In a live session, you can trace a small input step by step, compare expected and actual output, and test an edge case. Ask about the first step that does not make sense, then try a similar question yourself.

Explore coding tutoring · Request an eligible free 30-minute introduction. Your request is matched by subject and language; a tutor must accept before a time is confirmed.

برای مبحث C2.3 · مقایسه هزینه الگوریتم‌های مرتب‌سازی در درس ICS4U، سؤال و تلاش خود را همراه بیاورید. در جلسه می‌توانید یک ورودی کوچک را گام‌به‌گام دنبال کنید، خروجی مورد انتظار و واقعی را مقایسه کنید و یک حالت مرزی را بیازمایید. راهنمای معلم برنامه‌نویسی را ببینید یا جلسهٔ معارفهٔ رایگان ۳۰ دقیقه‌ای درخواست کنید. زمان جلسه پس از پذیرش معلم قطعی می‌شود.

About this lesson and its review

Published by DoAssignment. This reviewed lesson follows Ontario Grade 12 Computer Science (ICS4U), expectation C2.3. 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