Practical 1: Array Operations, Insert, Delete and Linear Search

Save that as array_lib.py. Every listing below imports from it, which is also how you should work: one file holds the structure and a second drives it, exactly as [Practical 6 continued: the Geometry Module, and pointyShapeVolume] did.

Six things in that class are the marks.

capacity and size are separate. The capacity never changes; the size does.

insert shifts from the right hand end backwards. Going forwards would overwrite the next value before it had been moved. That is the single commonest bug in this exercise, and the section after next shows it happening.

delete shifts forwards, from the gap towards the end, for the mirror reason.

The vacated slot is set to None. Not strictly necessary, but it means the array prints honestly and, in a language with real memory, it drops the reference so the object can be freed.

Every bound is checked and every failure raises rather than returning a code. Note that insert allows index == size, which is appending, while delete does not, because there is nothing there to delete.

The counters are for the journal, so the cost can be shown rather than claimed. insert returns how many values moved and delete returns the removed value and how many moved, which is why the driver below unpacks two things from delete.

Every operation run

from array_lib import Array


array = Array(8)
print("empty            ", array)

for value in [10, 20, 30, 40, 50]:
    array.append(value)
print("after 5 appends  ", array)

moved = array.insert(2, 99)
print(f"insert 99 at 2   ", array, f"  {moved} shift(s)")

moved = array.insert(0, 5)
print(f"insert 5 at 0    ", array, f"  {moved} shift(s)")

moved = array.insert(array.size, 60)
print(f"insert 60 at end ", array, f"  {moved} shift(s)")

removed, moved = array.delete(3)
print(f"delete index 3   ", array, f"  removed {removed}, {moved} shift(s)")

removed, moved = array.delete(0)
print(f"delete index 0   ", array, f"  removed {removed}, {moved} shift(s)")

removed, moved = array.delete(array.size - 1)
print(f"delete last      ", array, f"  removed {removed}, {moved} shift(s)")

print()
for target in [30, 10, 50, 77]:
    index = array.linear_search(target)
    found = f"at index {index}" if index >= 0 else "NOT FOUND"
    print(f"search {target:>3}  ->  {found:<12} after {array.comparisons} comparison(s)")

print()
print("total shifts made by this array:", array.shifts)

empty             []  size 0/8
after 5 appends   [10, 20, 30, 40, 50]  size 5/8
insert 99 at 2    [10, 20, 99, 30, 40, 50]  size 6/8   3 shift(s)
insert 5 at 0     [5, 10, 20, 99, 30, 40, 50]  size 7/8   6 shift(s)
insert 60 at end  [5, 10, 20, 99, 30, 40, 50, 60]  size 8/8   0 shift(s)
delete index 3    [5, 10, 20, 30, 40, 50, 60]  size 7/8   removed 99, 4 shift(s)
delete index 0    [10, 20, 30, 40, 50, 60]  size 6/8   removed 5, 6 shift(s)
delete last       [10, 20, 30, 40, 50]  size 5/8   removed 60, 0 shift(s)

search  30  ->  at index 2   after 3 comparison(s)
search  10  ->  at index 0   after 1 comparison(s)
search  50  ->  at index 4   after 5 comparison(s)
search  77  ->  NOT FOUND    after 5 comparison(s)

total shifts made by this array: 19

Read the shift counts against the positions. Inserting at the front of a six item array moved six values; inserting at the end moved none. Deleting the first item moved everything after it; deleting the last moved nothing. That asymmetry is the whole answer to "what does insertion in an array cost".

The bug the exercise is really about

Shifting in the wrong direction gives an answer that looks almost right, which is why it survives.

def insert_correctly(slots, size, index, value):
    for i in range(size, index, -1):
        slots[i] = slots[i - 1]
    slots[index] = value
    return size + 1


def insert_wrongly(slots, size, index, value):
    for i in range(index, size):
        slots[i + 1] = slots[i]
    slots[index] = value
    return size + 1


for label, function in [("backwards, correct", insert_correctly),
                        ("forwards, WRONG   ", insert_wrongly)]:
    slots = [10, 20, 30, 40, 50, None, None]
    size = function(slots, 5, 1, 99)
    print(f"{label} -> {slots[:size]}")

backwards, correct -> [10, 99, 20, 30, 40, 50]
forwards, WRONG    -> [10, 99, 20, 20, 20, 20]

The wrong one copies slot 1 into slot 2, then the new slot 2 into slot 3, and so on, so it smears the first value it touched all the way to the end. Shift from the far end towards the gap. For a delete it is the other way round, from the gap towards the far end, and for the same reason.

What the counts say about the cost

def insert_shifts(size, index):
    return size - index


def delete_shifts(size, index):
    return size - index - 1


size = 10
print(f"an array of {size} items")
print(f"{'position':>10} {'insert shifts':>15} {'delete shifts':>15}")
for index in [0, 1, 5, 9, 10]:
    ins = insert_shifts(size, index)
    dele = delete_shifts(size, index) if index < size else "n/a"
    print(f"{index:>10} {ins:>15} {str(dele):>15}")

print()
print("so, in Big O terms")
print("  at the END      : no shifting at all, O(1)")
print("  at the FRONT    : every item moves, O(n)")
print("  on average      : half the items move, which is still O(n)")
print("  reading a[i]    : arithmetic on the address, O(1)")
print("  linear search   : up to n comparisons, O(n)")

an array of 10 items
  position   insert shifts   delete shifts
         0              10               9
         1               9               8
         5               5               4
         9               1               0
        10               0             n/a

so, in Big O terms
  at the END      : no shifting at all, O(1)
  at the FRONT    : every item moves, O(n)
  on average      : half the items move, which is still O(n)
  reading a[i]    : arithmetic on the address, O(1)
  linear search   : up to n comparisons, O(n)

Reading is the array's strength and inserting in the middle is its weakness. That one sentence is the justification MU's Course Objective 8 asks for, and it is why [Practical 2: Building a Singly Linked List] exists.

Linear search, and the three variants an examiner asks for

def search_first(items, target):
    """The first match, or -1."""
    for index, item in enumerate(items):
        if item == target:
            return index
    return -1


def search_all(items, target):
    """Every position at which it occurs."""
    return [index for index, item in enumerate(items) if item == target]


def search_count(items, target):
    """How many times it occurs."""
    return sum(1 for item in items if item == target)


def search_sentinel(items, target):
    """The textbook trick: put the target at the end so the loop needs no bound test."""
    data = list(items) + [target]
    index = 0
    while data[index] != target:
        index += 1
    return index if index < len(items) else -1


marks = [45, 78, 45, 92, 45, 61]

for name, function in [("first ", search_first), ("all   ", search_all),
                       ("count ", search_count), ("sentinel", search_sentinel)]:
    print(f"{name}: 45 ->", function(marks, 45), "   99 ->", function(marks, 99))

first : 45 -> 0    99 -> -1
all   : 45 -> [0, 2, 4]    99 -> []
count : 45 -> 3    99 -> 0
sentinel: 45 -> 0    99 -> -1

The sentinel version is worth knowing because it appears in every textbook: putting a copy of the target at the end means the loop has only one test per step instead of two, since it cannot run off the end. It is a real optimisation in C and makes almost no difference in Python, and saying that is a better answer than either reciting it or not knowing it.

When a linear search is the right answer

An examiner may expect you to say binary search is better. It is not always.

def linear_search(items, target):
    comparisons = 0
    for index, item in enumerate(items):
        comparisons += 1
        if item == target:
            return index, comparisons
    return -1, comparisons


def binary_search(items, target):
    low, high, comparisons = 0, len(items) - 1, 0
    while low <= high:
        middle = (low + high) // 2
        comparisons += 1
        if items[middle] == target:
            return middle, comparisons
        if items[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return -1, comparisons


items = list(range(1000))

print(f"{'looking for':>12} {'linear':>8} {'binary':>8}")
for target in [0, 1, 500, 999, -1]:
    _, lin = linear_search(items, target)
    _, bin_ = binary_search(items, target)
    print(f"{target:>12} {lin:>8} {bin_:>8}")

print()
print("binary search needs the array SORTED. Sorting 1000 items costs about")
print("1000 x 10 = 10000 comparisons, so for a single search of an unsorted")
print("array, the linear one at 1000 comparisons is cheaper.")

 looking for   linear   binary
           0        1        9
           1        2       10
         500      501        9
         999     1000       10
          -1     1000        9

binary search needs the array SORTED. Sorting 1000 items costs about
1000 x 10 = 10000 comparisons, so for a single search of an unsorted
array, the linear one at 1000 comparisons is cheaper.

Look at the row for the target 0. Linear search found it in one comparison and binary search took nine, because it started in the middle and had to halve its way down to the first slot. Binary search wins overwhelmingly on average and loses on a first item, and it needs the array sorted first.

So the rule is a pair. Linear search for an unsorted array searched once. Binary search for a sorted array searched many times. That is the justification, and it is the shape of the answer MU's CO 8 wants.

Procedure

1. Save as practical2-1.py. Write the Array class with capacity, size, a slots list, and

__repr__ printing both the contents and the size out of the capacity.

1. Write append, raising OverflowError when full.
2. Write insert(index, value) shifting backwards from size down to index, with the bounds

checked and the number of shifts returned.

1. Write delete(index) shifting forwards, setting the vacated slot to None, returning the

removed value and the number of shifts.

1. Write linear_search(value) returning the index or -1 and counting its comparisons.
2. Run every operation, printing the array after each one with its shift count.
3. Write the wrong, forwards insertion and record what it does to the data.
4. Print the shift count table for insert and delete at several positions, and the Big O summary.
5. Search for something present and something absent and record both comparison counts.

Result

Every operation ran with the bounds checked. Inserting at the front of a six item array shifted six values and inserting at the end shifted none; deleting the first shifted every following item and deleting the last shifted none. The forwards insertion smeared one value across the rest of the array, which is the bug this exercise exists to teach. A search for a present value stopped at its index and a search for an absent value made one comparison per item. On 1000 sorted items, linear search found the first item in 1 comparison and the last in 1000, while binary search took 9 for the first, 10 for the last and never more than 10.

Where marks are lost

• Calling list.insert and list.remove. They hide the shifting, which is the exercise.
• Shifting in the wrong direction, which smears one value across the array.
• No capacity. Then it is a Python list and there is no full array to overflow.
• No bounds check, so a wrong index silently writes into a free slot.
• Not returning the removed value from delete.
• Returning 0 for "not found" in the search. 0 is a valid index; return -1 or raise.
• Not saying what the operations cost. Insert at the end is O(1) and at the front is O(n), and

the shift counts prove it.

• Only one search. Present and absent are two different runs.

For the journal

The aim in MU's words, all three bullets. The capacity and size picture with the arrow at the first free slot. The class in full. Then the run, with the array printed after every operation and its shift count beside it, because that column is the evidence for the costs. Then the wrong insertion and what it produced, with one sentence: shift from the far end towards the gap, or the value being moved is overwritten before it has been copied. Then the searches for a present and an absent value with their comparison counts. The conclusion: an array reads in one step and shifts to insert, so reading is O(1) and inserting or deleting anywhere but the end is O(n).

Quick revision

• An array is a fixed block of equal slots. Slot i is found by arithmetic, so reading is

O(1).

• capacity is how many slots exist; size is how many hold data. Keep both.
• Insert: shift backwards, from size down to index, then write. index == size is an

append.

• Delete: shift forwards, from index to size - 1, blank the last slot, decrease the

size.

• Shifting the wrong way smears one value over the rest.
• Insert at position i shifts size - i items; delete at i shifts size - i - 1.
• At the end O(1), at the front O(n), on average O(n).
• Linear search is O(n) and returns the index or -1, never 0 for absent.
• The sentinel trick saves one test per step and matters in C, not in Python.
• Linear search for an unsorted array searched once; binary search for a sorted array searched

often.

• Raise OverflowError when full and IndexError on a bad index.

Questions you should be able to answer

1. Why is reading a[500] no slower than reading a[0]? Because the address of slot i is the start plus i times the slot size, which is arithmetic rather than searching.

2. What is the difference between capacity and size? The capacity is how many slots the array has and never changes; the size is how many of them currently hold data.

3. Which way must the shifting go when inserting, and why? Backwards, from the last used slot towards the insertion point. Going forwards overwrites the next value before it has been copied, so one value is smeared across the rest.

4. How many items shift when you insert at position i in an array of size n? n - i. So none at the end and all n at the front.

5. What does insertion at the front cost, in Big O? O(n), because every item moves.

6. What should a linear search return when the value is absent, and why not 0? -1, or an exception. Zero is a valid index, so it cannot mean "not there".

7. When is linear search the better choice? When the array is not sorted and will be searched only once or a few times, because sorting it first to allow a binary search costs more than the linear searches would.

8. Give one case where linear search beats binary search. Looking for the first item: linear search finds it in one comparison, and binary search starts in the middle and took nine on 1000 items.

9. What should happen when you insert into a full array? An error. This class raises OverflowError, because an array cannot grow.

10. Why set the vacated slot to None after a delete? So the array prints honestly, and so the reference to the removed object is dropped and the object can be freed.