Lecture 4/6/2020
Agenda:
-
Algorithm analysis practice
-
Sorting
-
Selection sort
Whiteboard Notes:
Lecture 4/8/2020
Agenda:
-
Swap
-
isSorted
-
Bubble sort
Whiteboard Notes:
-
-
Edits: Swap notes have been cleaned up for clarity
-
Lecture 4/10/2020
Agenda:
-
Running time of sort
-
Worksheet: sorting
-
sortBalances.py
Clarifications:
-
The basic bubble sort we use in class is O(N^2). We can improve this algorithm by not checking the entire list in our inner loop. We can further optimize this alorithm by adding a flag that becomes true once the list is sorted. By adding a flag, we can achieve a best-case running time of O(N). But the worst-case performance is still O(N^2)
Handouts:
sortBalances.py
"""
Load the list of names and balances from balances.csv (comma delimited)
and output the contents sorted from highest balance to lowest.
"""
from swap import *
import random
import isSorted
def readFile(filename):
"""
Read in a comma delimited file consisting of names and integer balances
Parameter (string): filename to read
Return (list of [name,balance]):
returns a list of lists, where each sub-list contains a name (str)
and balance (int)
"""
file = open(filename, "r")
data = []
for line in file:
if line != "":
tokens = line.strip().split(",")
print(tokens[0], tokens[1])
accountInfo = [tokens[0], int(tokens[1])]
data.append(accountInfo)
return data
def outputBalances(balances):
"""
Print the names and balances from the given list
Names are printed with 25 space padding
Balances are printed with 10 space padding
Parameter: balances (lol of [name (str), balance (int)]
Return: None
"""
for i in range(len(balances)):
balance = balances[i]
print("%25s %10d"%(balance[0], balance[1]))
def bubbleSort(balances):
"""
Sort the list in place using bubble sort (decreasing order!)
Items are sorted based on balance
Param balances (lol of [name,balance]): the list to sort
Return: None
"""
for n in range(len(balances)):
for j in range(1,len(balances)-n):
if balances[j-1][1] < balances[j][1]:
swap(j-1, j, balances)
if __name__ == '__main__':
data = readFile("balances.csv")
bubbleSort(data)
outputBalances(data)