Sorting

Learning Objectives

At the end of this sub-unit, students should

understand the idea of simple sorting.
understand stable sorting.
know how to use built-in sorting.
know how to sort based on multiple criteria.

Sorted List

We know intuitively what we meant by a list that is sorted. But this is programming and we have to be precise. So how do we define what we meant by a sorted list more precisely? One general way is to say that the following property is satisfied.

\[ \text{if } i < j \text{ then } L[i] \leq L[j] \]

This is the definition for a list sorted in a non-decreasing way. It is non-decreasing because the element at the larger index cannot be smaller than the element at the smaller index. However, it need not always be larger. With this, we can actually specify 4 different kinds of sorting.

Category	Property
Non-Decreasing	\(\text{if } i < j \text{ then } L[i] \leq L[j]\)
Non-Increasing	\(\text{if } i < j \text{ then } L[i] \geq L[j]\)
Ascending	\(\text{if } i < j \text{ then } L[i] < L[j]\)
Descending	\(\text{if } i < j \text{ then } L[i] > L[j]\)

Most of the time, the case where \(L[i] = L[j]\) may not be interesting, but it will be useful for sorting on multiple properties later on.

Sorting Algorithm

For now, we will consider two simple sorting algorithms. There is no need to memorize these algorithms, simply knowing the idea is sufficient. At this point, we should be able to discuss idea. By knowing the idea, we expect readers should be able to implement their own version. Also, there are built-in sorting technique in Python.

Selection Sort

A typical way to explain selection sort is to play card games. When we are dealt cards during a game, we usually want to arrange the cards in smaller to larger. Assume that we have only unique numbers. In selection sort, we repeat the following process until there are no more cards in the original list.

Find the smallest card from the original list.
Take the card out
Put the card to the end of another sorted list.

How can we write this as code? The simplest one is to create another list to store the sorted cards.

Selection Sort

def selection_sort(lst):
  res = []
  while len(lst) > 0:
    tmp = min(lst)   # find the smallest card
    lst.remove(tmp)  # take the card out
    res.append(tmp)  # put it to the end of another sorted list
  return res

What if we do not want to create another list? Here, the idea is to swap this with the "front". However, the "front" changes after swapping. So instead of naming it the "front", we split the list into two parts: the sorted sublist and the rest of the sublist.

Now, our "front" is the front of the rest of the sublist. At the start, the sorted sublist is empty. Once we swap the smallest with the front of the rest of the sublist, this position becomes the end of the sorted sublist. We update the operation for selection sort to the following.

Pick the smallest element from the rest of the sublist.
Swap the smallest element with the front of the rest of the sublist.
- This extends the sorted sublist by one element.
- This decreases the rest of the sublist by one element.

The combination of the last two subpoints indicate that at the end, the list will only consist of the sorted sublist. In other words, the entire list is sorted.

Selection Sort

def selection_sort(lst):
  front = 0
  for _ in range(len(lst) - 1): # loop variable not used
    # find smallest in the rest
    smallest = front
    for i in range(front, len(lst)):
      if lst[i] < lst[smallest]:
        smallest = i
    # swap smallest with front
    lst[smallest], lst[front] = lst[front], lst[smallest]
    # extend the sorted sublist
    front = front + 1
  return lst

Bubble Sort

The idea for sort comes from the direct simplification of the property to be satisfied.

\[ \text{if } i < j \text{ then } L[i] \leq L[j] \]

We simplify this by looking only at adjacent elements.

\[ L[i] \leq L[i + 1] \]

Since \(i < i + 1\) is always true, we can remove the conditionals. We can work with this by using the following procedure until there is no more violations.

Compare each adjacent pair.
If the condition is not satisfied for the given pair, then we swap the pair.

Here is a nice simple reasoning why the above procedure will produce a sorted list. We will use the original property for any pair. So a violation is the following property.

\[ i < j \text{ and } L[i] > L[j] \]

Since the number of element is finite, there is only a finite number of violation.
Given a violation for adjacent pair, swapping them will reduce the total number of violations by one.
Eventually, there will be no more violation because we have a finite number of violations.
Hence, the list will be sorted.

Since the procedure has to be repeated until there is no more violation, we need to know when there is no more violation. We can do this by first iterating through the entire list at least once. If we ever swap any adjacent pair, we know that there is a violation. So that is how we can detect for violation. Put it another way, if there is no swap, we know that there are no more violations.

Now, there is one potential problem we may face. Since bubble sort relies on comparing adjacent pairs \(L[i]\) and \(L[i + 1]\). If we are enumerating the element from left to right, the rightmost element has the index of \(n - 1\) for a list of \(n\) element. But this \(n - 1\) must be produced by \(i + 1\) because if \(i = n - 1\), then \(i + 1 = n\) which is outside of the valid range. So it means we have to stop at \(i = n - 2\). This is why the loop is using range(len(lst) - 1).

Bubble Sort

def bubble_sort(lst):
  is_sorted = False
  while not is_sorted:
    is_sorted = True                             # rest flag
    for i in range(len(lst) - 1):
      if lst[i] > lst[i + 1]:                    # violation condition
        is_sorted = False                        # not sorted
        lst[i], lst[i + 1] = lst[i + 1], lst[i]  # swap
  return lst

Sorting Another Way

In our sorting algorithm, we only discuss sorting in non-decreasing order. If we want to sort this in another way, we have two possibilities.

Change the violation condition or selection condition.
- Selection Sort: Use max instead of min or introduce your own criteria.
- Bubble Sort: Compare with lst[i] < lst[i + 1] instead of lst[i] > lst[i + 1] or introduce your own condition.
Sort using the given algorithm and reverse the list.

Built-In Sort

There are two ways to sort in Python. The first is quite general for any iterables and the other only works with list.

Sort

The first way is only for list. There is a method for list called lst.sort(...). There are several ways to use this.

Usage	Description
`lst.sort()`	Sort the list in non-decreasing order using only `<` comparison between items.
`lst.sort(key=lambda arg: expr)`	Sort the list in non-decreasing order. Before items are compared with `<`, the `key` function is applied to the item (i.e., `key(item)`).
`lst.sort(reverse=True)`	Sort the list in non-increasing order.

We can also mix both additional arguments.

Sort

>>> lst = [2, 4, 3, 1, 5]
>>> lst
[2, 4, 3, 1, 5]
>>> lst.sort()
>>> lst
[1, 2, 3, 4, 5]
>>> lst.sort(key = lambda item: -item) # as if sorting [-1, -2, -3, -4, -5]
>>> lst   # notice key does not actually change the element
[5, 4, 3, 2, 1]
>>> lst.sort(key = lambda item: -item, reverse = True)
>>> lst
[1, 2, 3, 4, 5]

Notice how the arguments key and reverse are supplied with the name and the equal symbol. This is called keyword argument. In fact, for lst.sort(...), this is a keyword-only parameter. You do not have to know what these are, you simply need to know how to use key and reverse.

Sorted

The second way is to call the sorted function. The usage is similar to lst.sort(...) but we put the sequence as the first argument (i.e., sorted(seq, ...)).

Unlike lst.sort(...), the function sorted(seq, ...) can accept list, tuple, or other sequence. The return value will be a new list. If the sequence we want to sort is a list, sorted(lst, ...) will create a shallow copy of lst.

Sorted

>>> tpl = (2, 4, 3, 1, 5)
>>> sorted(tpl)
[1, 2, 3, 4, 5]
>>> lst = sorted(tpl)
>>> lst
[1, 2, 3, 4, 5]
>>> lst2 = sorted(lst, key = lambda item: -item)
>>> lst2
[5, 4, 3, 2, 1]
>>> lst  # unchanged
[1, 2, 3, 4, 5]

Stable Sort

The real advantage of key is when we have a a more complex type for our element. Consider a tuple where the first element is a string and the second element is an integer. If we wish to sort only based on the data of the second element, we can use key to extract the second element to be compared.

Key

>>> lst1 = [('D', 2), ('A', 4), ('B', 3), ('D', 1), ('B', 5)]
>>> lst2 = sorted(lst1)
>>> lst2  # sorted based the entire tuple
[('A', 4), ('B', 3), ('B', 5), ('D', 1), ('D', 2)]
>>> lst3 = sorted(lst2, key = lambda item: item[1])
>>> lst3  # sorted based only on second element
[('D', 1), ('D', 2), ('B', 3), ('A', 4), ('B', 5)]

Try to check the values of lst1 and lst2 at the end. Are they modified?

Now that we can sort a more complex type based on parts of it, there is a behavior that is interesting. Consider the comparison between ('D', 2) and ('D', 1). If the comparison is between the entire tuple, we can see that ('D', 1) is smaller than ('D', 2) so ('D', 1) must appear earlier in the sorted list.

What happen if we compare only based on the first element? Here, we expect the first element (i.e., 'D' for both) are actually equal. So which one comes first? If the relative ordering is unchanged, we say that the sorting is a stable sort. The built-in sorting technique is a stable sort.

Stable

>>> lst1 = [('D', 2), ('A', 4), ('B', 3), ('D', 1), ('B', 5)]
>>> lst2 = sorted(lst1, key = lambda item: item[0])
>>> lst2  # notice how ('D', 2) is before ('D', 1)
[('A', 4), ('B', 3), ('B', 5), ('D', 2), ('D', 1)]

As an example of a non-stable sort, our selection sort without additional list is not stable. We need to make a modification on the check into the following.

# other code omitted
if lst[i][0] < lst[smallest][0]:  # compare first element
# other code omitted

Stable

>>> lst1 = [('D', 2), ('A', 4), ('B', 3), ('D', 1), ('B', 5)]
>>> selection_sort(lst1)
[('A', 4), ('B', 3), ('B', 5), ('D', 1), ('D', 2)]

That is the property. But what is so special about stable sorting? The advantage of a stable sort is that we can solve the following kinds of problem.

Sort a list in non-decreasing order of the first element. For elements with equal value in the first element, we order them in non-increasing order of the second element.

That is quite a mouthful, so let us provide a simple example. Consider writing it as the table below. The version that is sorted by above is shown on the right.

Table

First Second

D 2

A 4

B 3

D 1

B 5
Sorted

First Second

A 4

B 5

B 3

D 2

D 1

Notice the second and third row. They have the same value of the first element, so if we look at the second element, they are in non-increasing order. Similarly for the fourth and fifth row. A nice visualization with partition is shown below.

Ordering

One way to solve this is obviously to write our own sorting algorithm. This can be done by copying any one of the sorting algorithms we have above and change the condition. For instance, the condition for the selection sort becomes the following.

# other code omitted
if (lst[i][0] < lst[smallest][0]) or ((lst[i][0] == lst[smallest][0]) and (lst[i][1] > lst[smallest][1])):
  # first element non-decreasing       first element equal            and second element non-increasing
# other code omitted

That is quite complicated. But at least it solves the problem. To use the stable sort property, we can do some trial and error. Here is what we are going to do. What is the effect of the following independently.

Sort the list in non-decreasing order of first element.
Sort the list in non-increasing order of second element.

Let us try these on Python.

Non-Decreasing First Element

sorted(lst,
       key = lambda item: item[0]
       reverse = False) # can be omitted

First	Second
A	4
B	3
B	5
D	2
D	1

Non-Increasing Second Element

sorted(lst,
       key = lambda item: item[1],
       reverse = True)

First	Second
B	5
A	4
B	3
D	2
D	1

If we look at the left table, the remaining problem is rather complicated.

Partition the list according to the value of the first element.
- All elements with the same value of first element is in one group.
Sort each partition in non-increasing order of second element.
- The sorting must be done independently of each other.

On the other hand, if we look at the right table, we know that the second element is already sorted in the way we want it to. Assuming that we are using a stable sort, the remaining problem is simply to sort the entire list in non-decreasing order. So the solution is the following.

>>> lst1 = [('D', 2), ('A', 4), ('B', 3), ('D', 1), ('B', 5)]
>>> lst1
[('D', 2), ('A', 4), ('B', 3), ('D', 1), ('B', 5)]
>>> lst2 = sorted(lst1, key = lambda item: item[1], reverse = True)
>>> lst2
[('B', 5), ('A', 4), ('B', 3), ('D', 2), ('D', 1)]
>>> lst3 = sorted(lst2, key = lambda item: item[0])
>>> lst3
[('A', 4), ('B', 5), ('B', 3), ('D', 2), ('D', 1)]

Can we generalize this? If so, how? The answer lies in the ordering. If we abstracted the sorting order, the question looks like the following.

Sorting order #1
For those with equal value, sorting order #2.

The way we perform the sorting is the reverse. We sort based on sorting order #2 first before sorting order #1. If we extend this into many sorting order, we get the following relationships. We simply have to reverse the order we perform the actual sorting. This works because sorting is stable.

Problem

# Sorting order #1
# Sorting order #2
#   :
# Sorting order #n

Solution

lst_n = sorted(lst_0, 'order #n')
#  :
lst_2 = sorted(lst_3, 'order #2')
lst_1 = sorted(lst_2, 'order #1')