CS 111 Lecture: Sorting

Table of Contents

  1. Sorting with the key parameter
  2. Sorting with list methods

Question: How to sort by elements that are not in the first position?

Here is a list of the Space Missions where the second element in the tuple represents the number of days the mission lasted. Some quick terminology:

  • Program name refers to 'Apollo' or 'Mercury-Redstone', for example
  • Mission number refers to the 11 in 'Apollo 11' or '3' in Gemini 3
  • Days refers to the number of days the mission lasted. In truth, many of the missions with one day listed lasted only a matter of minutes but have been rounded to 1 for ease.
In [1]:
missions = [('Apollo 11', 8), ('Mercury-Redstone 3', 1),
            ('Apollo 13', 5), ('Gemini 3', 1), ('Little Joe 6', 1)]
In [2]:
sorted(missions)
Out[2]:
[('Apollo 11', 8),
 ('Apollo 13', 5),
 ('Gemini 3', 1),
 ('Little Joe 6', 1),
 ('Mercury-Redstone 3', 1)]

Our Problem: How to sort the missions not by name (default), but by days?

1. Sorting with the key parameter

Yes! It turns out, the function sorted allows us to perform sorting by using the key parameter, which specifies the element of an item to use for sorting.

In [3]:
help(sorted)
Help on built-in function sorted in module builtins:

sorted(iterable, key=None, reverse=False)
    Return a new list containing all items from the iterable in ascending order.
    
    A custom key function can be supplied to customise the sort order, and the
    reverse flag can be set to request the result in descending order.

In [4]:
def days(missionTuple):
    return missionTuple[1]
In [5]:
sorted(missions, key=days)
Out[5]:
[('Mercury-Redstone 3', 1),
 ('Gemini 3', 1),
 ('Little Joe 6', 1),
 ('Apollo 13', 5),
 ('Apollo 11', 8)]
In [6]:
# define the function missionLength that will return the length of the 
# entire name of the mission (i.e., length of "Apollo 11")
def missionLength(missionTuple):
    return len(missionTuple[0])
In [7]:
# use the function missionLength for sorting with key
sorted(missions, key=missionLength)
Out[7]:
[('Gemini 3', 1),
 ('Apollo 11', 8),
 ('Apollo 13', 5),
 ('Little Joe 6', 1),
 ('Mercury-Redstone 3', 1)]

YOUR TURN: Write functions that will allow you to sort by mission number, name of program (i.e., Apollo, Gemini, ..etc.), and length of mission name:

In [8]:
# define the function missionNumber that will return the mission number from the tuple (mission, days)
# As a reminder, the mission number refers to 11 in 'Apollo 11'
# The return value should be an int
def missionNumber(missionTuple):
    return int(missionTuple[0].split()[-1])
In [9]:
# use the function missionNumber for sorting key
sorted(missions, key=missionNumber)
Out[9]:
[('Mercury-Redstone 3', 1),
 ('Gemini 3', 1),
 ('Little Joe 6', 1),
 ('Apollo 11', 8),
 ('Apollo 13', 5)]
In [10]:
# define the function programName that will return the name of the program from the tuple (mission, days)
# As a reminder, the program name refers to 'Apollo' in 'Apollo 11'
# This is tricky!  You will need to use slicing and the .join() method because a program name could potentially 
# be multiple words.
def programName(missionTuple):
    return ''.join(missionTuple[0].split()[:-1])
In [11]:
# use the function programName for sorting with key. 
sorted(missions, key=programName)
Out[11]:
[('Apollo 11', 8),
 ('Apollo 13', 5),
 ('Gemini 3', 1),
 ('Little Joe 6', 1),
 ('Mercury-Redstone 3', 1)]

More complex sorting

Things get more complicated in situations where elements in a list to be sorted have the same key, and we want to sort by a second key. For example consider the following mission tuples:

In [12]:
missions2 = [('Big Joe 1', 1), ('Mercury-Atlas 3', 1), ('Apollo 9', 10), 
           ('Gemini 10', 2), ('Gemini 3', 1), ('Gemini 9', 3)]


sorted(missions2) # sorts by mission name by default
Out[12]:
[('Apollo 9', 10),
 ('Big Joe 1', 1),
 ('Gemini 10', 2),
 ('Gemini 3', 1),
 ('Gemini 9', 3),
 ('Mercury-Atlas 3', 1)]
In [13]:
sorted(missions2, key=days) # sorts by days
Out[13]:
[('Big Joe 1', 1),
 ('Mercury-Atlas 3', 1),
 ('Gemini 3', 1),
 ('Gemini 10', 2),
 ('Gemini 9', 3),
 ('Apollo 9', 10)]

The resulting tuples are indeed sorted by days, but how to explain the order for items with the same days?

Python's sorting functions/methods are stable, which means that items that are equal according to the sorting key have the same relative order as in the original list. (Verify this in the above example.)

How can we sort tuples with the same days alphabetically by the mission number and then the program number?

IMPORTANT: The code below expects you to have defined missionNumber, programName, and days in the exercises above.

In [14]:
# A key function that returns a tuple to specify 
# lexicographic ordering by the elements of that tuple. 
def daysNumProgram(missionTuple):
    return (days(missionTuple), missionNumber(missionTuple), programName(missionTuple))

sorted(missions2, key=daysNumProgram)
Out[14]:
[('Big Joe 1', 1),
 ('Gemini 3', 1),
 ('Mercury-Atlas 3', 1),
 ('Gemini 10', 2),
 ('Gemini 9', 3),
 ('Apollo 9', 10)]

YOUR TURN: Below, define numDaysLength so that the it sorts all tuples in missions and missions2 in ascending order first by

  • the number of the program, then
  • by the number of days the mission lasted,
  • then by the length of the program name:

HINT: Make use of the helper functions you created previously.

In [15]:
# Your code here for the definition of numDaysLength
def numDaysLength(missionTuple):
    return missionNumber(missionTuple), days(missionTuple), programName(missionTuple)

sorted(missions+missions2, key=numDaysLength)
Out[15]:
[('Big Joe 1', 1),
 ('Gemini 3', 1),
 ('Gemini 3', 1),
 ('Mercury-Atlas 3', 1),
 ('Mercury-Redstone 3', 1),
 ('Little Joe 6', 1),
 ('Gemini 9', 3),
 ('Apollo 9', 10),
 ('Gemini 10', 2),
 ('Apollo 11', 8),
 ('Apollo 13', 5)]

2. Sorting with mutating list methods

Python list objects have their methods to sort a list in place (i.e., by mutating the existing list, not returning a new list):

In [16]:
numbers = [35, -2, 17, -9, 0, 12, 19]
In [17]:
numbers.sort()

Notice that nothing was returned.

In [18]:
numbers
Out[18]:
[-9, -2, 0, 12, 17, 19, 35]

Notice that the original list was mutated.

We can reverse the order of items in the list, without sorting:

In [19]:
numbers2 = [35, -2, 17, -9, 0, 12, 19]
numbers2.reverse()
In [20]:
numbers2
Out[20]:
[19, 12, 0, -9, 17, -2, 35]

If we want to reverse the order of a sorted list, we need to sort it firt and then reverse:

In [21]:
numbers2 = [35, -2, 17, -9, 0, 12, 19]
numbers2.sort()
numbers2.reverse()
In [22]:
numbers2
Out[22]:
[35, 19, 17, 12, 0, -2, -9]
In [23]:
help(numbers2.sort)
Help on built-in function sort:

sort(...) method of builtins.list instance
    L.sort(key=None, reverse=False) -> None -- stable sort *IN PLACE*

Notice that sort can take the same parameters key and reverse as sorted.

Here is an alternative way of sorting a list in reverse order using sort and passing reverse as an argument.

In [24]:
numbers3 = [35, -2, 17, -9, 0, 12, 19]
numbers3.sort(reverse=True)
numbers3
Out[24]:
[35, 19, 17, 12, 0, -2, -9]