I'm currently doing the shelf problem (fairly well-known, I hope?). Essentially, I am given the scenario of a shelf (set) of blocks (elements), and I am supposed to rearrange them according to their size. This is part of an introduction to insertion sort.
The first part of this problem involves me writing a function insert_animation(block_pos, shelf, high). This function takes in a shelf of blocks of varying sizes, for example, [Block size: 2, Block size: 6, Block size: 1, Block size: 4, Block size: 8, Block size: 3, Block size: 9]. I am given the functions shelf.insert(position, block), which inserts a block at a given position, and shelf.pop(position), which removes an element at position.
For this problem, I am supposed to first pop the element at the index (integer) block_pos from the shelf, compare the popped element with each element within the range from 0 to high, then insert the popped element just before an element with equal or larger value. If there is no such value (i.e. the popped element is bigger than everything), the popped element will be inserted at the position of high (i.e. the last position of the range).
I suppose I understand the logic, and have come up with such a code:
def insert_animate(block_pos, shelf, high):
if block_pos == 0:
return shelf
p = shelf.pop(block_pos)
for i in range(high):
if p.size <= shelf[i].size:
shelf.insert(i, p)
break
else:
shelf.insert(high, p)
return shelf
To my frustration, it seems as if the "break" statement just refuses to do what I say, and more and more elements keep getting inserted in.
For example, let s = [Block size: 2, Block size: 6, Block size: 1, Block size: 4, Block size: 8, Block size: 3, Block size: 9] (this is a code that requires a programme given by professors to run, and will not work on Python alone).
Suppose now I want print(insert_animate(3, s, 3)). I would expect
[Block size: 2, Block size: 4, Block size: 6, Block size: 1, Block size: 8, Block size: 3, Block size: 9]
where the block of size 4 is popped and inserted just before block of size 6. Reasonable, I hope?
But with my code above, I get
[Block size: 2, Block size: 4, Block size: 6, Block size: 1, Block size: 4, Block size: 8, Block size: 3, Block size: 9]
The problem, as it seems to me, is that the break just isn't working, and the for i in range(high)
loop simply keeps running and keeps inserting the block of size 4 whenever the condition is met.
I've been cracking my head over this for hours today but can't figure out a way around it. This is just the tip of the iceberg of all my problems subsequently, but I figured this is the root of the issue, so if anyone can offer any advice on this particular matter, I would really appreciate it!!!
TLDR: Use for:...else: with nested if:, instead of for: with a nested if:...else:. The else: clause of a for loop triggers only if no break was executed in the loop – this corresponds to having found no valid position, thus needing to insert the element at the end.
The code currently insert p for every element that is not smaller, until a smaller one is found:
def insert_animate(block_pos, shelf, high):
if block_pos == 0:
return shelf
p = shelf.pop(block_pos)
for i in range(high):
if p.size <= shelf[i].size:
shelf.insert(i, p)
break # stop once smaller element is found
else: # triggers *for each i* with p.size > shelf[i].size
shelf.insert(high, p) # insert until loop is stopped
return shelf
Change it to trigger only if all elements are not smaller:
def insert_animate(block_pos, shelf, high):
if block_pos == 0:
return shelf
p = shelf.pop(block_pos)
for i in range(high):
if p.size <= shelf[i].size:
shelf.insert(i, p)
break
else: # triggers *for all i* with p.size > shelf[i].size
shelf.insert(high, p) # insert at most once
return shelf