You are previewing Programming Python, 4th Edition.

Reversing and Sorting Sequences

The permutation utilities of the prior section are useful in a variety of applications, but there are even more fundamental operations that might seem prime candidates for automation. Reversing and sorting collections of values, for example, are core operations in a broad range of programs. To demonstrate coding techniques, and to provide examples that yield closure for a recurring theme of this chapter, let’s take a quick look at both of these in turn.

Implementing Reversals

Reversal of collections can be coded either recursively or iteratively in Python, and as functions or class methods. Example 18-23 is a first attempt at two simple reversal functions.

Example 18-23. PP4E\Dstruct\Classics\rev1.py

```def reverse(list):               # recursive
if list == []:
return []
else:
return reverse(list[1:]) + list[:1]

def ireverse(list):              # iterative
res = []
for x in list: res = [x] + res
return res```

Both reversal functions work correctly on lists. But if we try reversing nonlist sequences (strings, tuples, and so on), the `ireverse` function always returns a list for the result regardless of the type of sequence passed:

```>>> `ireverse("spam")`
['m', 'a', 'p', 's']```

Much worse, the recursive `reverse` version won’t work at all for nonlists—it gets stuck in an infinite loop. The reason is subtle: when `reverse` reaches the empty string (`""`), it’s not equal to the empty list (`[]`), so the `else` clause is selected. But slicing an empty sequence returns another empty sequence (indexes are scaled): ...