B. Software Development · Software Development: Problem Solving, Design, Testing and the Life Cycle

Algorithms to Specification: Inserting and Deleting in a Sorted Array

B3.1About 70 minutes

Learning goals

I can read a specification for an algorithm, including its inputs, outputs and the conditions it must keep true.
I can design and code an algorithm that inserts a value into a sorted array so that it stays sorted.
I can design and code an algorithm that deletes a value from the middle of an array by shifting the later items.
I can test these algorithms with extreme cases: empty arrays, the first and last positions, duplicates and values that are not found.

Words to know

specification (spec)
A precise description of what an algorithm or program must do: its inputs, outputs and rules, including special cases. It says what, not how.

sorted (ascending) array
An array whose items are in order from smallest to largest, so each item is less than or equal to the next.

shift
Copying items one position left or right to close a gap or make room.

precondition
Something that must be true before the algorithm runs, for example "the list is already sorted".

postcondition
Something the algorithm guarantees is true when it finishes, for example "the list is still sorted and has one more item".

index
The position number of an item in an array. Python indexes start at 0.

Keeping things in order

A leaderboard in a game, a class list in alphabetical order, the times in a ski race: all are sorted arrays. When a new score arrives, you could add it at the end and sort the whole list again, but that wastes work. Instead, you can slide it straight into the right place. When someone leaves, you remove them and close the gap.

In Arrays and Subprograms you learned to create lists, use indexes and loop through them. In this lesson you will design algorithms to a specification: given an exact description of what must happen, you will plan, code and test an algorithm that meets it.

Reading a specification

A good specification says what must happen, not how:

Inputs: a list arr sorted in ascending order (the precondition) and a number value.
Output / effect: arr contains value and is still in ascending order (the postcondition). The length grows by 1.
Special cases: the list may be empty; value may be smaller than everything, larger than everything, or equal to an item already there.

Before coding, list the test cases the spec suggests. That way you design for the extreme cases from the start, instead of discovering them later as bugs.

Worked example

Example 1: Designing the insert algorithm

Insert 25 into the sorted list [10, 20, 30, 40, 50] without sorting the whole list again. Plan the algorithm in steps, then trace it.

Make room: add the value at the end, so the list is one longer: [10, 20, 30, 40, 50, 25]. Our "hole" is at the last index, 5.
Shift bigger items right: look at the item just to the left of the hole. If it is bigger than 25, copy it into the hole, and the hole moves one place left.
50 > 25: copy → [10, 20, 30, 40, 50, 50], hole at 4. 40 > 25: copy → hole at 3. 30 > 25: copy → hole at 2.
Stop when the item to the left is not bigger (20 < 25), or when the hole reaches index 0 (the value is the smallest).
Place 25 in the hole: [10, 20, 25, 30, 40, 50]. ✓

Append, shift bigger items right one at a time, then place the value in the gap.

Inserting 25. Each row shows one step, and the highlighted cell is the one that changed. Items bigger than 25 are copied one place right until the gap reaches the right spot.

def insert_sorted(arr, value):

"""Insert value into the ascending list arr, keeping it sorted."""

arr.append(value) # make room at the end

i = len(arr) - 1

while i > 0 and arr[i - 1] > value:

arr[i] = arr[i - 1] # shift the bigger item right

i = i - 1

arr[i] = value

scores = [10, 20, 30, 40, 50]

insert_sorted(scores, 25)

print(scores)

insert_sorted(scores, 5)

insert_sorted(scores, 60)

print(scores)

Output: [10, 20, 25, 30, 40, 50], then [5, 10, 20, 25, 30, 40, 50, 60]. The tests include a value smaller than everything (5) and larger than everything (60).

Why i > 0 and ...? If the value is the smallest, the hole reaches index 0 and there is nothing to its left. Checking i > 0 first stops the loop before it reads arr[-1] (which in Python would quietly read the last item, a nasty hidden bug). Because and stops at the first False, the second test is never reached.

Worked example

Example 2: Designing the delete algorithm

Specification: remove the first copy of value from arr. Return True if it was found and removed, False if it was not there (and leave arr unchanged). Delete 30 from [10, 20, 30, 40, 50].

Search: a linear search finds 30 at index 2. If the search fails, return False straight away.
Shift left: from the found position to the second-last index, copy each next item one place left: arr[2] = arr[3] gives [10, 20, 40, 40, 50]; arr[3] = arr[4] gives [10, 20, 40, 50, 50].
Shrink: the last item is now a leftover copy, so remove it with arr.pop(): [10, 20, 40, 50].
The list stays sorted automatically, because the order of the remaining items never changed.

Find the position, shift every later item one place left, remove the last slot.

Deleting 30. Each later item is copied one place left over the gap, and the leftover last slot is removed.

def delete_value(arr, value):

"""Remove the first copy of value from arr. Return True if found."""

pos = -1

for i in range(len(arr)):

if arr[i] == value:

pos = i

break

if pos == -1:

return False

for i in range(pos, len(arr) - 1):

arr[i] = arr[i + 1] # shift left over the gap

arr.pop() # drop the extra last item

return True

scores = [10, 20, 30, 40, 50]

print(delete_value(scores, 30), scores)

print(delete_value(scores, 99), scores)

Output: True [10, 20, 40, 50] and then False [10, 20, 40, 50], since 99 is not in the list, so nothing changes.

Test case	Input	Expected result
empty list	insert 7 into []	[7]
new smallest	insert 1 into [2, 4, 6, 8, 10]	[1, 2, 4, 6, 8, 10]
new largest	insert 60 into [..., 50]	60 at the end
duplicate	insert 8 into [3, 8, 8, 12]	[3, 8, 8, 8, 12]
delete only item	delete 4 from [4]	True, []
delete missing	delete 1 from []	False, []
delete a duplicate	delete 7 from [5, 7, 7, 9]	True, [5, 7, 9] (first 7 removed)

Extreme-case tests for both algorithms. Both functions in this lesson pass every one of them.

How much work?

Inserting near the front of a list of n items needs about n shifts; inserting near the end needs very few. Deleting is the same. For a class list of 30 that is nothing, but for millions of items it matters, which is why later courses (such as ICS4U) study faster data structures.

Python's shortcuts

Python lists have built-in methods that do the shifting for you: arr.insert(index, value), arr.remove(value) and arr.pop(index), and the bisect module's bisect.insort(arr, value) inserts into a sorted list. In real projects you would use them. In this course you must also be able to design these algorithms yourself, because many languages have only fixed-size arrays, and because designing them builds the skills you need for algorithms that no library provides.

a = [10, 20, 30, 40, 50]

a.insert(2, 25)

print(a)

a.remove(40)

print(a)

import bisect

b = [10, 20, 30]

bisect.insort(b, 15)

print(b)

Output: [10, 20, 25, 30, 40, 50] / [10, 20, 25, 30, 50] / [10, 15, 20, 30] (one line each)

Just for fun

Sorting a deck of cards by inserting each new card into its place in your hand is a real sorting algorithm with an official name: insertion sort. You have probably been running it at family card games for years.

Hands-on activity

Human array

You need: 6 to 8 index cards or sticky notes, a marker, and a table. (A deck of playing cards with the face cards removed also works.)

Write numbers on 5 cards and lay them in a row in ascending order, with gaps between. Write the index (0, 1, 2, ...) on paper under each position.
Insert: pick a new number. Put it in a new position at the right end. Following the algorithm exactly, move only one card at a time, and only into the empty spot next to it. Count the moves.
Delete: remove a card from the middle and close the gap by sliding later cards left one at a time. Count the moves.
Try the extreme cases: insert a number smaller than all the others; delete the first card; insert a duplicate.
Then code insert_sorted and delete_value yourself, without looking, and test them with the cases from the table above.

What to look for: inserting the smallest number into 5 cards takes 5 moves; inserting the largest takes 0 moves; the cards are still sorted after every operation.

Your turn

Write the precondition and postcondition for insert_sorted.

Trace insert_sorted([3, 9, 15], 10). How many items are shifted?

How many shifts does inserting 1 into [2, 4, 6, 8, 10] need?

Trace delete_value([4, 8, 12, 16], 8). What does it return and what is the list after?

What does delete_value([4, 8, 12], 5) return? Is the list changed?

Why must the insert loop check i > 0 before arr[i - 1] > value?

Name three extreme cases you should test for an insert-into-sorted-list algorithm.

More practice: warm-up

Is [5, 9, 9, 14] sorted in ascending order?

What is the index of the first item in a Python list?

In the delete algorithm, which direction do later items shift?

What does [10, 20, 30].insert(1, 15) change the list to?

What does a specification describe: what an algorithm does, or how it does it?

More practice: on your own

Insert "Leo" into the alphabetical list ["Ali", "Chen", "Maya", "Zoe"] with the same algorithm. Which items move?

Change insert_sorted so it works for a list sorted in descending order (largest first). Which one character changes?

Write a function delete_at(arr, pos) that removes the item at index pos by shifting. What does it do to [3, 6, 9, 12] with pos = 0?

For a sorted list of 1000 items, what are the fewest and the most shifts an insert can need? When does each happen?

A spec says: "Remove every copy of value". Does delete_value meet it? Give a test that shows the answer.

Challenge

In many languages an array has a fixed size, so you store a count of how many slots are used. Describe how to insert into a sorted fixed-size array arr that holds count items, and what must happen when count equals the array's size.

Write an algorithm (pseudocode or Python) to merge two sorted lists into one sorted list, such as [2, 7, 9] and [3, 4, 10] → [2, 3, 4, 7, 9, 10], without sorting from scratch.

A leaderboard keeps only the top 5 scores in descending order. Specify (inputs, outputs, special cases) a function add_score(board, score).

Check your understanding

Quiz

After insert_sorted(arr, 12) with arr = [5, 10, 15, 20], what is arr?

How many items shift when 3 is inserted into [4, 6, 8]?

To delete an item from the middle of an array, later items are:

Which is a postcondition of insert_sorted?

What does delete_value([1, 2, 3], 9) return?

Why test inserting a value smaller than every item?

For parents and teachers

Big idea: B3.1 asks students to design simple algorithms according to specifications, such as adding data to a sorted array and deleting a datum from the middle of an array. The key skills are reading a specification precisely and testing extreme cases.

How to help: Do the "human array" activity with cards together; moving one card at a time makes the shifting idea concrete. Ask "What if the list is empty? What if the number is smaller than all of them?"

Common difficulties:

Shifting in the wrong direction or the wrong order, which overwrites values before they are copied.
Off-by-one errors in the loop range (len(arr) - 1 in the delete loop).
Forgetting the extreme cases: empty list, first position, last position, value not found.
Using arr.insert() or sort() when the assignment asks for the algorithm itself.