Sorting
Andrew S. Fitz Gibbon
UW CSE 160
Winter 2023
1
sorted vs. sort
my_lst = [5, 3, 4, 2]
print(sorted(my_lst)) 🡪 [2, 3, 4, 5]
print(my_lst) 🡪 [5, 3, 4, 2]
my_lst.sort()
print(my_lst) 🡪 [2, 3, 4, 5]
2
Returns a new sorted list
Does not modify original list
Modifies the list in place, returns None
sorted vs. sort example
hamlet = "to be or not to be that is the question whether tis nobler in the mind to suffer".split()
print("hamlet:", hamlet)
print("sorted(hamlet):", sorted(hamlet))
print("hamlet:", hamlet)
print("hamlet.sort():", hamlet.sort())
print("hamlet:", hamlet)
3
Modifies the list in place, returns None
Returns a new sorted list (does not modify the original list)
Customizing the sort order
Goal: sort a list of names by last name
names = ["Isaac Newton", "Albert Einstein", "Niels Bohr", "Marie Curie", "Charles Darwin", "Louis Pasteur", "Galileo Galilei", "Margaret Mead"]
print("names:", names)
This does not work:
print("sorted(names):", sorted(names))
When sorting, how should we compare these names?
"Niels Bohr"
"Charles Darwin"
4
Aside: What does this do?
def mystery(msg):
return msg.split(" ")[1]
x = mystery("happy birthday")
print(x)
5
Sort key
fruits = ["watermelon", "fig", "apple"]
print(sorted(fruits))
print(sorted(fruits, key=len))
6
Sort key
def last_name(name):
return name.split(" ")[1]
print('last_name("Isaac Newton"):', last_name("Isaac Newton"))
* Another aside: This doesn't get everyone's last names and is not how you'd sort by names in Real Life™
7
Use a sort key as the key argument
Supply the key argument to the sorted function or the sort function
def last_name(name):
return name.split(" ")[1]
names = ["Isaac Newton", "Ada Lovelace", "Fig Newton", "Grace Hopper"]
print(sorted(names, key=last_name))
print(sorted(names, key=len))
def last_name_len(name):
return len(last_name(name))
print(sorted(names, key=last_name_len))
8
If there is a tie in last names, preserves original order of values.
itemgetter is a function�that returns a function
Useful for creating a function that will return particular elements from a sequence (e.g., list, string, tuple):
import operator
operator.itemgetter(2)([7, 3, 8]) 🡪 8
operator.itemgetter(0)([7, 3, 8]) 🡪 7
operator.itemgetter(1)([7, 3, 8]) 🡪 3
operator.itemgetter(0, 1)([7, 3, 8]) 🡪 (7, 3)
operator.itemgetter(3)([7, 3, 8]) 🡪
IndexError: list index out of range
9
Returns a function
Call function passing in this list as an argument
A tuple
Read the Documentation: https://docs.python.org/3/library/operator.html
itemgetter Exercise
import operator
lst1 = [2, 7, 3, 9, 4]
print(operator.itemgetter(1)(lst1))
print(operator.itemgetter(1, 2)(lst1))
print(operator.itemgetter(2, 3)(lst1))
tup2 = operator.itemgetter(3, 2, 1, 0)(lst1)
print(tup2)
print(operator.itemgetter(0)(tup2))
get_second = operator.itemgetter(1)
print(get_second(tup2))
print(operator.itemgetter(2)("howdy"))
print(operator.itemgetter(2, 0, 1)("howdy"))
10
Tuples
student_score = ('Robert', 8)
11
Two ways to Import itemgetter
import operator
student_score = ('Robert', 8)
operator.itemgetter(0)(student_score) ⇒ “Robert”
operator.itemgetter(1)(student_score) ⇒ 8
Or
from operator import itemgetter
student_score = ('Robert', 8)
itemgetter(0)(student_score) ⇒ “Robert”
itemgetter(1)(student_score) ⇒ 8
12
A tuple
Another way to import, allows you to call itemgetter directly.
Using itemgetter
from operator import itemgetter
student_score = ('Robert', 8)
itemgetter(0)(student_score) ⇒ “Robert”
itemgetter(1)(student_score) ⇒ 8
student_scores =
[('Robert', 8), ('Alice', 9), ('Tina', 7)]
Sort the list by name:
sorted(student_scores, key=itemgetter(0))
Sort the list by score
sorted(student_scores, key=itemgetter(1))
13
Another way to import, allows you to call itemgetter directly.
What does: sorted(student_scores) return?
Sorting based on two criteria
Goal: sort based on score;� if there is a tie within score, sort by name
Two approaches:
Approach #1: Use an itemgetter with two arguments
Approach #2: Sort twice (most important sort last)
student_scores = [('Robert', 8), ('Alice', 9),
('Tina', 10), ('James', 8)]
Approach #1:
sorted(student_scores, key=itemgetter(1,0))
Approach #2:
sorted_by_name = sorted(student_scores, key=itemgetter(0))� sorted_by_score = sorted(sorted_by_name, key=temgetter(1))
14
Sort on most important criteria LAST
from operator import itemgetter
student_scores = [('Robert', 8), ('Alice', 9), ('Tina', 10), ('James', 8)]
sorted_by_name = sorted(student_scores, key=itemgetter(0))�>>> sorted_by_name
[('Alice', 9), ('James', 8), ('Robert', 8), ('Tina', 10)]
sorted_by_score = sorted(sorted_by_name, key=itemgetter(1))
>>> sorted_by_score
[('James', 8), ('Robert', 8), ('Alice', 9), ('Tina', 10)]
15
More sorting based on two criteria
If you want to sort different criteria in different directions, you must use multiple calls to sort or sorted
student_scores = [('Robert', 8), ('Alice', 9), \
('Tina', 10), ('James', 8)]
Goal: sort score from highest to lowest; if there is a tie within score, sort by name alphabetically (= lowest to highest)
sorted_by_name = sorted(student_scores, key=itemgetter(0))�sorted_by_hi_score = sorted(sorted_by_name, key=itemgetter(1), reverse=True)
16
Remember: Sort on most important criteria LAST
Sorting Exercise
from operator import itemgetter
student_scores = [('Ann', 7), ('Raul', 6), ('Ted', 4), ('Lisa', 6)]
print(sorted(student_scores, key=itemgetter(1)))
lst_a = sorted(student_scores, key=itemgetter(0))
print(lst_a)
lst_b = sorted(lst_a, key=itemgetter(1))
print(lst_b)
lst_c = sorted(lst_a, key=itemgetter(1), reverse=True)
print(lst_c)
17
Digression: Lexicographic Order
18
'Aaron'
'Andrew'
'Angie'
'with'
'withhold'
'withholding'
[1, 9, 9]
[2, 1]
[3]
[1]
[1, 1]
[1, 1, 1]
'Able'
'Charlie'
'baker'
'delta'
[1, 1]
[1, 1, 2]
[1, 2]
Sorting: strings vs. numbers
>>> sorted([125, 5, 3125, 625, 25])
[5, 25, 125, 625, 3125]
>>> sorted(["125", "5", "3125", "625", "25"])
['125', '25', '3125', '5', '625']
19
Aside: Use a sort key to create a new list
Create a different list that contains the value returned by the sort key, sort it, �then extract the relevant part:
names = ["Isaac Newton", "Fig Newton", "Niels Bohr"]
# keyed_names is a list of [lastname, fullname] lists
keyed_names = []
for name in names:
keyed_names.append([last_name(name), name])
sorted_keyed_names = sorted(keyed_names)
sorted_names = []
for keyed_name in sorted_keyed_names:
sorted_names.append(keyed_name[1])
print("sorted_names:", sorted_names)
20
1) Create the new list.
2) Sort the list new list.
If there is a tie in last names, sort by next item in list: fullname
3) Extract the relevant part.
Itemgetter Examples
import operator
operator.itemgetter(2, 7, 9, 10)("dumbstricken")
operator.itemgetter(2, 5, 7, 9)("homesickness")
operator.itemgetter(2, 7, 9, 10)("pumpernickel")
operator.itemgetter(2, 3, 6, 7)("seminaked")
operator.itemgetter(1, 2, 4, 5)("smirker")
# Could even return elements in a different order
operator.itemgetter(9, 7, 6, 1)("beatnikism")
operator.itemgetter(14, 13, 5, 1)("Gedankenexperiment")
operator.itemgetter(12, 10, 9, 5)("mountebankism")
21
Returns a function
Call function passing in this string as an argument