Sorting
Jessica Xu
Nov 15, 2024
CSCI 110 - Lecture 34
Today’s Agenda
|
|
| |
| |
| |
| |
Quiz
Time for Quiz 9!
Good luck!
Note: You can Mark/Test your code :)
Sorting
Sorting
Take a collection of items and organize them in a specific way!
Sorting in Computer Science
Take an iterable (list, string, set, dictionary) and put the individual items in a specific order!
Sorting Lists
Lists have a built-in instance method named sort:
my_list = [10, 8, 20, 1, -3, 7]
my_list.sort()
print(my_list)
[-3, 1, 7, 8, 10, 20]
Sorting Strings
my_string = “xaybaza”
my_string.sort()
print(my_string)
AttributeError: 'str' object has no attribute 'sort'
Sorting Iterables
For anything that is not a list (strings, dictionaries, etc.), use the sorted() function.
my_string = "xaybaza"
sorted(my_string)
print(my_string)
my_string = "xaybaza"
new_string = sorted(my_string)
print(new_string)
"xaybaza"
["a", "a", "a", "b", "x", "y", "z"]
Descending Order
The sort() method and sorted() function both take in reverse=True as a optional parameter to indicate descending order.
my_list = [10, 8, 20, 1, -3, 7]
my_list.sort(reverse=True)
print(my_list)
my_string = "xaybaza"
new_string = sorted(my_string, reverse=True)
print(new_string)
[20, 10, 8, 7, 1, -3]
["z", "y", "x", "b", "a", "a", "a"]
Upper case vs. Lower case?
words = ["apples", "Bananas", "Yams", "carrots"]
words.sort()
print(words)
["Bananas", "Yams", "apples", "carrots"]
Key function
The sort() method and sorted() function both take in key as an optional parameter to indicate a function to be run on each item when comparing them.
w = ["apples", "Bananas", "Yams", "carrots"]
w.sort(key=str.lower)
print(w)
s = "aXbYCz"
s2 = sorted(s, key=str.lower)
print(s2)
["apples", "Bananas", "carrots", "Yams"]
["a", "b", "C", "X", "Y", "z"]
Lambda function
A special type of function in Python that allows you to define a function in one line without a name (also called an anonymous function) and without a return statement. It will always return the results of the expression.
lambda arguments : expression
Lambda function
lambda arguments : expression
Example:
x = lambda a : a * 10
print(x(5))
Equivalent:
def mutiply_10(num)
return num * 10
print(multiply_10(5))
50
Lambda function
lambda arguments : expression
Example:
y = lambda a, b, c : a + b + c
print(y(5, 10, 20))
Equivalent:
def sum_all(a, b, c)
return a + b + c
print(sum_all(5, 10, 20))
35
Sorting 2D Lists
Can use lambda functions combined with key to define how we want to sort something that doesn’t have an obvious order.
my_2d_list = [[10, 1, 5], [8, 20, 1], [-3, 7, 8]]
my_2d_list.sort(key=lambda nums: nums[2])
print(my_2d_list)
[[8, 20, 1], [10, 1, 5], [-3, 7, 8]]
Sorting Classes
woodie = Character("Woodie", 15, 5)
pickie = Character("Pickie", 12, 10)
jessica = Character("Jessica", 99, 99)
character_list = [woodie, pickie, jessica]
character_list.sort(key=lambda character : character.strength)
print(character_list)
[pickie, woodie, jessica]
Stable Sorts
Sorts are guaranteed to be stable. This means that if two items have the same key, their order will be preserved in the output.
my_2d_list = [[10, 1, 5], [8, 20, 1], [-3, 7, 5]]
my_2d_list.sort(key=lambda nums: nums[2])
print(my_2d_list)
[[8, 20, 1], [10, 1, 5], [-3, 7, 5]]
Stable Sorts
Thus if we want to use a “tie breaker” to sort by multiple field we can just sort twice! First by the secondary, then by primary key.
my_2d_list = [[10, 1, 5], [8, 20, 1], [-3, 7, 5]]
my_2d_list.sort(key=lambda nums: nums[0])
[[-3, 7, 5], [8, 20, 1], [10, 1, 5]]
my_2d_list.sort(key=lambda nums: nums[2])
[[8, 20, 1], [-3, 7, 5], [10, 1, 5]]
Tuples as Tie Breakers
Alternatively we can achieve the same thing by having our lambda functions evaluate to a tuple of (primary, secondary).
my_2d_list = [[10, 1, 5], [8, 20, 1], [-3, 7, 5]]
my_2d_list.sort(key=lambda nums: (nums[2], nums[0]))
[[8, 20, 1], [-3, 7, 5], [10, 1, 5]]
Sorting Algorithms!
Many many many sorting algorithms! All achieve the same thing:
Sorting Algorithms!
They differ in their strategies. They each have their strengths and weaknesses depending on the input:
https://www.toptal.com/developers/sorting-algorithms
Sorting Runtime
Different sorting algorithms also have different runtimes.
The default sort in every programming language has time complexity:
O(n log(n))
Runtime
def drop_lowest_two_grades(grades):
grades.sort(reverse=True)
grades.pop()
grades.pop()
return sum(grades) / len(grades)
O(nlog(n))
Time Complexity:
O(n log(n)) + O(1) + O(n)
= O(n log(n))
O(1)
O(n)
Runtime
def drop_lowest_half_of_grades(grades):
grades.sort(reverse=True)
for i in range(len(grades) / 2):
grades.pop(i)
return sum(grades) / len(grades)
O(nlog(n))
O(n)
O(n)
O(n)
Time Complexity:
O(n log(n)) + O(n) * O(n) + O(n)
= O(n log(n)) + O(n^2) + O(n)
= O(n^2)
Questions?
Reminders
Interview Prep Bootcamp! TOMORROW!
Reminder: Project 2 (pt. 3)
Reminder there are no late submissions for the projects!
Reminder: Project 2 (pt. 4)
Will be released next Monday and due the following Monday!
Don’t forget the extra credit (practice problems) that is due on Wednesday November 27th @ 11:59pm!
Reminder: HW 11
Retake: Quiz 9
Final Exam
When: During your lab on Tuesday, December 3rd!
Where: TBD
Afterwards, there will be an Engineering Director from Google who has volunteered their time to give you a Tech Talk on Tuesday, December 3rd @ 4pm!
Grades!
Googler TAs and Career Coaches!
Need some extra support?
Book virtual OH with some folks from Google!
https://sites.google.com/corp/view/gir-career-coaches
Email my Googler TAs: