This chapter focuses on sorting of Python lists. In particular, it discusses the sorting of a list of numbers, from low to high. The techniques discussed, however, are not limited to just the sorting of lists of numbers – with a few small adaptations they can be used to sort anything.
You probably know that Python lists have a built-in sort() method, which, when applied to a list of numbers, does exactly what the chapter discusses. So why would I see the need to discuss methods of sorting? The reasons are threefold:
sort() method, you might get into a situation where you have to sort something that is not a list, and you have to implement your own method. This chapter will show you how to do that.To be able to understand discussions on the manipulation of Python lists, you need to know something about how Python has implemented lists.
Python has implemented lists as “arrays”. An array is a sequential block of computer memory that is divided into chunks of equal size, in such a way that each chunk contains one array element. Because the array consists of one sequential block of memory, it is very speedy for the computer to locate an element with a particular index.
An example illustrates this. Suppose that I have an array of 10 elements, each element having a size of 8 bytes. The first element (the one with index 0) starts at memory address 62560000 (in decimal numbers). Since the array consists of a sequential block of memory, the second element (index 1) will be at memory address 62560008, the third at memory address 62560016, etc. To find the element with index i, the computer needs to take the memory address of the first element, and add to that i times the size of each chunk – in this case: 62560000 + i * 8. Since for a computer accessing a memory address of which you know the number is a very fast operation, an array is an effective way of implementing a list.
It is not all good news, however. Arrays are notoriously rigid when you need to manipulate them. Most programming languages which use arrays force you to specify at the start how big the array should be. Python does not do that, it allows you to vary the length of the list. How exactly this is implemented I don’t know, but it might happen that when you make a list grow longer and longer, at some point Python needs to pick up the whole list and put it somewhere else in memory, as there is no more room for the list to grow. Alternatively, Python may have implemented a method whereby some parts of the list exist somewhere else in memory. Regardless, Python needs to solve some issues to allow lists of variable length.
Moreover, while, in general, it is cheap to add a new element to the end of an array (append()), it is expensive to insert a new element in the middle or at the start of an array (insert()). The reason is that inserting requires the programming language to move all elements with an index greater than or equal to the place where the new element is inserted, one place upwards in memory. You can imagine that that is implemented according to the following idea:
# insert num into tlist at index i.
def my_insert( tlist, num, i ):
if i < 0 or i > len( tlist ):
return
tlist.append( tlist[-1] ) # add the last element of tlist once more at the end
for j in range( len( tlist )-1, i, -1 ): # move up every element at or after i one place in the array
tlist[j] = tlist[j-1]
tlist[i] = num
numlist = [0,1,2,3,4,5,6,7,8,9,10]
my_insert( numlist, 99, 5 )
print( numlist )
Such an implementation of inserting is O(n) with n being the length of the list (i.e., in the worst-case scenario a new element is inserted at the start of the list, which means that every element needs to be copied once). Thus, inserting is a pretty slow process.
If you want to have a data structure that is more efficient at inserting elements in a list, you can use a “linked list”. This will be discussed in a later chapter.
There are two different ways of approaching sorting algorithms.
The first is to use two lists: the original list that is to be sorted, and a new list that is sorted. Elements from the original list are taken and removed, and inserted into the new list. Once the original list is empty, the new list is the sorted version.
The second way uses only the original list, and sorts it “in-place”. Usually the approach is that the list is considered to be partly sorted, e.g., the front end of the list (with the lowest indices) is sorted, and the back end is still unsorted. Elements are moved from the back end to the front end, and put in their rightful place, until the unsorted part of the list is empty.
Of several of the sorting algorithms below I discuss both ways of implementing them. In practice, usually only the “in-place” version is used, but often the first way is a bit easier to understand.