Repeating Until It Is Done
Putting a list in order
Take a list along once, swapping neighbors that are the wrong way round, and count the comparisons, the swaps and the passes that putting a whole list in order takes.
Searching a list that is in no particular order means looking at every value in the worst case, and that is the price of the list being in no particular order. So how does a list get into order in the first place? The plainest way needs nothing you have not already met: compare a value with the one next to it, and if they are the wrong way round, swap them. Do that all the way along and you have made one pass.
One pass, and what a pass is worth
A pass goes along the list comparing each value with the one to its right, swapping whenever the left one is the larger. A list of n values has n − 1 neighboring pairs, so a pass makes n − 1 comparisons however jumbled or tidy the list is — the comparisons are the same either way, and only the swaps change. What a pass buys you is one value: the largest one is carried along by every comparison it takes part in until it reaches the end, so after one pass it is certainly in its final place. Everything else may still be wrong, which is why passes are repeated. A list of n values never needs more than n − 1 of them, and it is finished the moment a pass makes no swap at all.
Worked example
What does this program print? It makes one pass along its list.
values = [4, 8, 3, 6]
for i in range(0, 3):
if values[i] > values[i + 1]:
left = values[i]
values[i] = values[i + 1]
values[i + 1] = left
print(values[0])
print(values[3])First trip, i is 0: compare 4 with 8. 4 is not larger, so nothing is swapped and the list is still 4, 8, 3, 6.
A comparison that changes nothing is still a comparison, and it still costs the same as one that does.
Try it together
A list of 6 values is being put in order, and on the third pass no swap happens at all.
Nothing to trace here — it is all counting.
1.How many comparisons does a single pass along 6 values make?
Have a go
Have a go on your own. What does this program print?
values = [6, 2, 5]
for i in range(0, 2):
if values[i] > values[i + 1]:
left = values[i]
values[i] = values[i + 1]
values[i + 1] = left
print(values[2])Ready to practice?
Eight questions on what you have just read. Nothing is timed, and you can play as many times as you like.