A. Programming Concepts and Skills · Arrays and Subprograms

Inserting, Deleting and Parallel Lists

A1.6 A2.3 A3.2 A4.4About 70 minutes

Learning goals

I can insert a value into a sorted list by shifting elements, keeping it sorted.
I can delete an element from the middle of a list by shifting elements left.
I can use parallel lists to store related data and keep them in step.
I can use a list of counters (a tally array) to count how often each value occurs.

Words to know

shift
To move a group of elements one position left or right to make or close a gap.

sorted insertion
Adding a value to a sorted list in the one position that keeps the list sorted.

parallel lists (parallel arrays)
Two or more lists where the elements at the same index belong together, e.g. names[i] and marks[i].

tally (frequency) array
A list of counters where the index stands for a value and the element counts how many times it appeared.

fixed-size array
An array whose length cannot change, as in Java or C. Inserting and deleting must be done by shifting.

Keeping a leaderboard in order

An arcade at a winter carnival shows the scores so far, always sorted. When a new score comes in, it must slide into the right place. When a player is disqualified, their score must be removed and the gap closed. Python's insert and pop do this for you, but in most languages arrays have a fixed size, and the programmer moves the elements by hand. Knowing how gives you a real feel for what an array is, and it is a classic exercise in designing an algorithm to a specification.

Inserting into a sorted list

Make room: add a spare slot at the end.
Start at the last old element. While it is bigger than the new value, copy it one place right.
Stop at the first element that is not bigger (or at the front). Put the new value in the gap just after it.

Working from the end matters: if you shifted from the front, each copy would overwrite the next value before it moved.

Inserting 25 into [10, 20, 30, 40]. 40 and 30 (blue) each move one place right; 20 is not bigger than 25, so 25 (green) goes into index 2.

def insert_sorted(values, x):

"""Insert x into the ascending list values, keeping it sorted."""

values.append(x) # make room at the end

i = len(values) - 2 # last old element

while i >= 0 and values[i] > x:

values[i + 1] = values[i] # shift right

i -= 1

values[i + 1] = x

scores = [10, 20, 30, 40]

insert_sorted(scores, 25)

print(scores)

insert_sorted(scores, 5)

insert_sorted(scores, 99)

print(scores)

Output: [10, 20, 25, 30, 40] then [5, 10, 20, 25, 30, 40, 99]. The tests include the middle, the front (5) and the end (99).

Deleting from the middle

To remove the element at index k: copy each later element one place left, starting at k, then remove the last slot, which is now a duplicate. This time you must work from the front, so you never overwrite a value you still need.

def delete_at(values, index):

"""Remove the element at index by shifting later elements left."""

for i in range(index, len(values) - 1):

values[i] = values[i + 1]

values.pop() # the last slot is now a duplicate

line_up = ["Ava", "Ben", "Cy", "Dev", "Eli"]

delete_at(line_up, 1)

print(line_up)

Output: ['Ava', 'Cy', 'Dev', 'Eli']. Cy, Dev and Eli each moved one place left; the extra copy of Eli at the end was popped.

Worked example

Example 1: Trace a sorted insertion

Trace insert_sorted([3, 8, 12], 9) and show the list after each step.

Append 9 for room: [3, 8, 12, 9]. i = 2.
values[2] = 12 > 9: shift → [3, 8, 12, 12]; i = 1.
values[1] = 8 > 9? No: stop.
values[i + 1] = values[2] = 9 → [3, 8, 9, 12].

[3, 8, 9, 12]

Parallel lists

Sometimes each item has several pieces of data: a student's name and mark. One way to store them is parallel lists: two lists of the same length where index i in both refers to the same student. To look up a mark, linear-search the names list for the index, then use that index in the marks list.

Parallel lists: the dashed lines join elements that share an index. Index 2 (shaded) is Priya, mark 91.

names = ["Aiyana", "Jonah", "Priya", "Marc"]

marks = [88, 74, 91, 67]

def mark_of(name):

"""Return the mark for name, or -1 if the name is not found."""

for i in range(len(names)):

if names[i] == name:

return marks[i]

return -1

def top_student():

"""Return the name of the student with the highest mark."""

best = 0

for i in range(1, len(marks)):

if marks[i] > marks[best]:

best = i

return names[best]

print(mark_of("Jonah"), mark_of("Zoe"))

print(top_student())

Output: 74 -1 and Priya. The rule for parallel lists: every change must happen to both lists at the same index (insert, delete, swap when sorting), or the data will no longer match.

Tally arrays: counting each value

To count how often each value appears, use the value as an index into a list of counters. You saw this with dice in Using Built-in Functions and Modules. It works whenever the values are small whole numbers.

ratings = [4, 5, 3, 5, 2, 5, 4, 1, 5, 4] # survey answers 1 to 5

counts = [0] * 6 # index 0 unused

for r in ratings:

counts[r] += 1

for score in range(1, 6):

print(score, "#" * counts[score])

Output: a bar chart made of # signs, one row per rating (shown below). Multiplying a string by a whole number repeats it: "#" * 3 is "###".

1 #

2 #

3 #

4 ###

5 ####

Output of the tally program: one 1, one 2, one 3, three 4s and four 5s.

Worked example

Example 2: Delete from parallel lists

Marc has moved to another school. Remove him from names and marks so the lists stay matched.

Find Marc's index with a linear search: index 3.
Delete index 3 from both lists: names.pop(3) and marks.pop(3) (or delete_at on each).
Deleting from only one list would shift nothing in this case (Marc is last), but deleting Jonah from only names would pair Priya with 74. Always change both.

names becomes ["Aiyana", "Jonah", "Priya"] and marks becomes [88, 74, 91].

Just for fun

Parallel lists are like a pair of mittens on a string: perfectly useful, until one of them gets lost and the other has no idea what it belongs to.

Hands-on activity

Human leaderboard

You need: 6 to 8 index cards, a pen, a table, and a computer with Python.

Write a score on each of 5 cards and lay them in increasing order, leaving space for one more card at the right.
Write a new score. Insert it by the algorithm: starting from the right end, slide each card that is bigger one place right; when you reach a card that is not bigger, drop the new card in the gap. Count the slides.
Delete the second card: slide every card after it one place left, starting with the closest one.
On a second row of cards, write a player name under each score (parallel lists). Repeat steps 2 and 3 while keeping the name cards matched.
Code insert_sorted and delete_at and test them with the same numbers, including inserting a value smaller than all the others and one larger than all of them.

What to look for: the student shifts from the right when inserting and from the left when deleting, and keeps both rows matched.

Your turn

Show the list after inserting 15 into [5, 10, 20, 30] while keeping it sorted. Which elements shift?

Show the list after deleting index 0 from [7, 3, 9] by shifting.

Why does sorted insertion shift starting from the end?

names = ["Ali", "Bea"] and ages = [16, 17]. Write code that prints each name with its age.

What does counts[r] += 1 do in a tally array?

Predict: insert_sorted([2, 4], 1) then print the list.

More practice: warm-up

What are parallel lists?

Inserting into a list of length 6 gives a list of length ...?

In a tally of dice rolls 1 to 6, how long should the counts list be if the roll is used as the index?

What does "#" * 3 give?

To delete from the middle, do you shift elements left or right?

More practice: on your own

Trace delete_at([4, 8, 15, 16, 23], 2).

Write delete_value(values, x) that removes the first x using a linear search and delete_at. What should it do if x is missing?

Write code that counts how many students got each Ontario level, given levels = [4, 3, 3, 2, 4, 1, 3].

With names and marks from the lesson, write class_average() and then print the names of students above it.

A student sorts marks with marks.sort() but does not touch names. What goes wrong?

Challenge

How many element moves does insert_sorted make in the worst case for a list of n elements? When does that happen?

Write merge(a, b) that takes two sorted lists and returns one sorted list containing all elements, without calling sort.

Write code that finds the most common rating (the mode) in ratings from the tally example, using the counts list.

Check your understanding

Quiz

Inserting 6 into [2, 4, 8, 10] keeping it sorted gives:

To delete the element at index 1 of a fixed-size array, you should:

names = ["A", "B", "C"], marks = [70, 85, 60]. What is B's mark?

After counts = [0] * 4 and for x in [1, 3, 3]: counts[x] += 1, what is counts?

Why must parallel lists be changed together?

When inserting into a sorted list, where does the shifting start?

For parents and teachers

Big idea: These algorithms deepen A1.6 (modifying arrays) and A2.3 (nested algorithms on arrays). Inserting into a sorted array and deleting from the middle are also the curriculum's examples for designing algorithms to a specification, which the Software Development unit builds on. Tracing (A4.4) is essential here.

How to help: The card leaderboard is the clearest way to see shifting. Ask, "Which card moves first? Why that one?"

Common difficulties:

Shifting in the wrong direction or order, which copies one value over the rest.
Off-by-one in the shift loops (the last element is missed, or an IndexError happens).
Changing one parallel list but not the other.
Using a tally array for values that are not small whole numbers (e.g. negative numbers or decimals), which gives an index error or wrong counts.