sorting (class slides)
CSC 110 – Sorting
Announcements
- Pay attention do dates
- Final exam: Dec 13, Friday – 6:00pm - 8:00pm in S SCI 100
- Projects 11 and 12 due on WEDNESDAY, Dec 11
Sorting
- A number of reasons to want sorted data
- For doing binary search!
- Finding a median value
- Finding the min and max
- Others?
Sorting
- lists have built-in functionality to rearrange the elements to be in sorted order
- list_var.sort()
- sorted(list_var)
- But, someone at some point had to come up with an algorithm for this!
- How does sorting work, behind the scenes?
What is a sorted list?
- A sorting algorithm is an algorithm that puts elements of a list in a certain order
- However, there are different types of “ordering”
- Ascending numeric order (numbers)
- Descending numeric order (numbers)
- Lexicographic (strings)
- Others…
- We will mostly stick with Ascending numeric for the examples in this lecture
What is a sorted list?
Not sorted
[5, 10, 20, 6, 7, 9, 43, 10, 12]Sorted
[5, 6, 7, 9, 10, 10, 12, 20, 43]Discuss
Come up with a sorting algorithm
Discuss ideas for how to sort numbers
Depict your algorithm with drawings/diagrams or with pseudocode
Can’t use the .sort() method
In-place and out-of-place
In-place sorting: does not require a secondary data structure
Out-of-place sorting: may require a secondary data structure
Out-of-place sorting
- Create a new empty list
- Find the min on the original list, remove it from original, add to new
- Repeat until original list is empty
Quiz 11
You have 10 minutes to complete the quiz
- No need for comments, no need for a
main(), no test cases
Built-in functions you can use: round(), input(), float(), str(), int(), len(), range(), set(), list() — you don’t have to use all of these
Survey
Selection sort
Selection sort is a very simple sorting algorithm
Scan the list and find the smallest element
Swap this element with the beginning element
Continue these steps for the remaining list, not including the element just swapped
Repeat
Selection sort
Visualizing sorting algorithms with graphics can give one a better understanding
Write selection sort
- Function name is
selection_sort - It takes a list as argument
- It mutates the list argument, sorting it
- It iterates over the list, scanning the list to find the smallest element
- It swaps the smallest element found in each iteration with the beginning element (start with beginning element at zero indes, add one to beginning index with each iteration)
Write selection sort – solution
def find_min_index(items):
min_index = None
for i in range(len(items)):
if min_index == None or items[min_index] > items[i]:
min_index = i
return min_index
def selection_sort(items):
begin_index = 0
while begin_index < len(items)-1:
# get min of sublist, add begin_index to shift it
min_index = find_min_index(items[begin_index:]) + begin_index
items[begin_index], items[min_index] = items[min_index], items[begin_index]
begin_index += 1
def main():
test_list = [5, 10, 20, 6, 7, 9, 43, 10, 12]
selection_sort(test_list)
print(test_list)
main()[5, 6, 7, 9, 10, 10, 12, 20, 43]How many total sweeps and swaps to sort this list?
How many total sweeps and swaps to sort this list?
[3, 1, 7, 2, 4] sweep
[1, 3, 7, 2, 4] swap and sweep
[1, 2, 7, 3, 4] swap and sweep
[1, 2, 3, 7, 4] swap and sweep
[1, 2, 3, 4, 7] swap
4 sweeps
4 swaps (worst case scenario)
How many total sweeps and swaps to sort this list?
How many total sweeps and swaps to sort this list?
[ 3, 1, 7, 2, 4, 8, 5 ] sweep
[ 1, 3, 7, 2, 4, 8, 5 ] swap and sweep
[ 1, 2, 7, 3, 4, 8, 5 ] swap and sweep
[ 1, 2, 3, 7, 4, 8, 5 ] swap and sweep
[ 1, 2, 3, 4, 7, 8, 5 ] swap and sweep
[ 1, 2, 3, 4, 5, 8, 7 ] swap and sweep
[ 1, 2, 3, 4, 5, 7, 8 ] swap
6 sweeps, 6 swaps
Attendance on gradescope
Bubble sort
Bubble Sort: another sorting algorithm
Scan through each element in the list, comparing the current element with the next one
If the next one is smaller, swap the elements
Continue these iterations until the whole list is sorted
This causes the large elements to “bubble up” to the top
Write bubble sort
- Function name is
bubble_sort - It takes a list as argument
- It mutates the list, sorting it
- It iterates over the list, comparing each element with the next one, if the next one is smaller, swap elements
- It continues these iterations until the whole list is sorted
Write bubble sort – solution 1
def bubble_sort(items):
end = len(items)-1
for i in range(len(items)-1):
for j in range(end):
if items[j] > items[j+1]:
items[j], items[j+1] = items[j+1], items[j]
end -=1
def main():
test_list = [5, 10, 20, 6, 7, 9, 43, 10, 12]
bubble_sort(test_list)
print(test_list)
main()[5, 6, 7, 9, 10, 10, 12, 20, 43]8 sweeps, 10 swaps
Swaps
[5, 10, 20, 6, 7, 9, 43, 10, 12]
[5, 10, 6, 20, 7, 9, 43, 10, 12]
[5, 10, 6, 7, 20, 9, 43, 10, 12]
[5, 10, 6, 7, 9, 20, 43, 10, 12]
[5, 10, 6, 7, 9, 20, 10, 43, 12]
[5, 10, 6, 7, 9, 20, 10, 12, 43]
[5, 10, 6, 7, 9, 20, 10, 12, 43]
[5, 6, 10, 7, 9, 20, 10, 12, 43]
[5, 6, 7, 10, 9, 20, 10, 12, 43]
[5, 6, 7, 9, 10, 20, 10, 12, 43]
[5, 6, 7, 9, 10, 10, 20, 12, 43]
[5, 6, 7, 9, 10, 10, 12, 20, 43]
Write bubble sort – solution 2
def bubble_sort(items):
is_sorted = False
end = len(items)-1
while not is_sorted:
is_sorted = True
for i in range(end):
if items[i] > items[i+1]:
items[i], items[i+1] = items[i+1], items[i]
is_sorted = False
end -= 1
def main():
test_list = [5, 10, 20, 6, 7, 9, 43, 10, 12]
bubble_sort(test_list)
print(test_list)
main()[5, 6, 7, 9, 10, 10, 12, 20, 43]3 sweeps, 10 swaps
How many total sweeps and swaps to sort this list?
How many total sweeps and swaps to sort this list?
[ 3, 1, 7, 2, 4 ] first sweep
[ 1, 3, 7, 2, 4 ] swap
[ 1, 3, 2, 7, 4 ] swap
[ 1, 3, 2, 4, 7 ] swap
[ 1, 3, 2, 4, 7 ] second sweep
[ 1, 2, 3, 4, 7 ] swap
[ 1, 2, 3, 4, 7 ] third sweep
How many total sweeps and swaps?
How many total sweeps and swaps?
[ 3, 1, 7, 2, 4, 8, 5 ] first sweep
[ 1, 3, 7, 2, 4, 8, 5 ] swap
[ 1, 3, 2, 7, 4, 8, 5 ] swap
[ 1, 3, 2, 4, 7, 8, 5 ] swap
[ 1, 3, 2, 4, 7, 5, 8 ] swap
[ 1, 3, 2, 4, 7, 5, 8 ] second sweep
[ 1, 2, 3, 4, 7, 5, 8 ] swap
[ 1, 2, 3, 4, 5, 7, 8 ] swap
[ 1, 2, 3, 4, 5, 7, 8 ] third sweep
Attendance
Go to gradescope and answer today’s attendance question
Lots of algorithms
There are many sorting algorithms
Bogo sort
Selection sort
Bubble sort
Insertion sort
Merge sort
Quick sort
...more...