sorting (slides)

CSC 110 – Sorting

Sorting

A number of reasons to want sorted data
- For doing binary search!
- Finding a median value
- Finding the min and max
- Others?

What is a sorted list?

A sorting algorithm is an algorithm that puts elements of a list in a certain order
There are different types of “ordering”:

# ascending numeric order 
numbers = [1, 2, 3, 4, 8, 10]

# descending numeric order
numbers = [20, 17, 5, 3, 1]

# lexicographic
letters = ['a', 'b', 'c', 'e']

Sorting

Two built-in functions, compare their difference:

list_var.sort()

items = [5, 10, 20, 6, 7, 9, 43, 10, 12]
items.sort()
items

[5, 6, 7, 9, 10, 10, 12, 20, 43]

sorted(list_var)

items = [5, 10, 20, 6, 7, 9, 43, 10, 12]
sorted(items)
items

[5, 10, 20, 6, 7, 9, 43, 10, 12]

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

Selection sort

Selection sort uses in-place sorting

Watch visualization and describe: how selection sort works?
https://visualgo.net/en/sorting

Selection sort

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

Write selection sort - step 1

Function name is find_min_index
It takes a list of numbers as argument
It iterates over the list, scanning the list to find the smallest number
Return the index of the smallest number

assert find_min_index([]) == None
assert find_min_index([5, 10, 1, 20, 7, 3, 9]) == 2

Write selection sort – step 1 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 main():
  test_list = [5, 10, 1, 20, 7, 3, 9]
  assert find_min_index(test_list) == 2
  
main()

Write selection sort - step 1 continue

Now you found the index of smallest number, let’s make one swap: swap the items at index 0 and min_index.

items = [5, 10, 1, 20, 7, 3, 9]

begin_index = 0
min_index = find_min_index(items) # min_index is 2

# swap items at index 0 and 2
items[begin_index], items[min_index] = items[min_index], items[begin_index]

assert items = [1, 10, 5, 20, 7, 3, 9]

Write selection sort - step 2

How to find the min_index starting from begin_index? You can call find_min_index function.

begin_index = 1
items = [1, 10, 5, 20, 7, 3, 9]

# write your code here

assert min_index == 5

Write selection sort - step 2 solution

How to find the min_index starting from begin_index? You can call find_min_index function.

begin_index = 1
items = [1, 10, 5, 20, 7, 3, 9]

assert items[begin_index:] == [10, 5, 20, 7, 3, 9] 

# index of 3 in the sublist is 4
assert find_min_index(items[begin_index:]) == 4  

# index of 3 in the list is 5
min_index = find_min_index(items[begin_index:]) + begin_index 
assert min_index == 5

Write selection sort - step 2 continue

Now you found the index of smallest number starting from begin_index, let’s make another swap:

items = [1, 10, 5, 20, 7, 3, 9]

begin_index = 1
min_index = find_min_index(items[begin_index:]) + begin_index 

# swap items at index 1 and 5
items[begin_index], items[min_index] = items[min_index], items[begin_index]

assert items = [1, 3, 5, 20, 7, 10, 9]

Write selection sort - step 3

Function name is selection_sort that mutates the list argument and sort it
Iterate over the list, call find_min_index to find the index of smallest element
Swap the smallest element found in each iteration with the beginning one
Use a while loop, set a begin_index before loop, in each iteration add 1 to begin_index

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)
  assert test_list == [5, 6, 7, 9, 10, 10, 12, 20, 43]
  
main()

How many total sweeps and swaps to sort this list?

numbers = [ 3, 1, 7, 2, 4 ]

How many total sweeps and swaps?

[ 3, 1, 7, 2, 4 ] sweep, begin_index: 0

[ 1, 3, 7, 2, 4 ] swap and sweep, begin_index: 1

[ 1, 2, 7, 3, 4 ] swap and sweep, begin_index: 2

[ 1, 2, 3, 7, 4 ] swap and sweep: begin_index: 3

[ 1, 2, 3, 4, 7 ] swap

4 sweeps, 4 swaps (worst case scenario)

How many total sweeps and swaps to sort this list?

numbers = [ 3, 0, 7, 2, 4, 8 ]

How many total sweeps and swaps to sort this list?

[ 3, 0, 7, 2, 4, 8 ] sweep

[ 0, 3, 7, 2, 4, 8] swap and sweep

[ 0, 2, 7, 3, 4, 8 ] swap and sweep

[ 0, 2, 3, 7, 4, 8 ] swap and sweep

[ 0, 2, 3, 4, 7, 8 ] swap and sweep

5 sweeps, 4 swaps

Attendance

How many total sweeps and swaps to sort this list?

[ 7, 1, 1, 4, 2 ]

Bubble sort

Bubble Sort: another sorting algorithm
1. Scan through each element in the list, comparing the current element with the next one
2. If the next one is smaller, swap the elements
3. Continue these iterations until the whole list is sorted
This causes the large elements to “bubble up” to the top

Write bubble sort - step 1

Function name is single_sweep_swap
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 sweeps the list only once

assert single_sweep_swap([8, 3, 5, 7, 1]) == [3, 5, 7, 1, 8]

Write bubble sort – step 1 solution

def single_sweep_swap(numbers):
    end = len(numbers) - 1
    for i in range(end):
        if numbers[i] > numbers[i+1]:
            numbers[i], numbers[i+1] = numbers[i+1], numbers[i]
    return numbers

def main():
    assert single_sweep_swap([8, 3, 5, 7, 1]) == [3, 5, 7, 1, 8]
    assert single_sweep_swap([3, 5, 7, 1, 9]) == [3, 5, 1, 7, 9]
    
main()

Write bubble sort - step 2

Function name is bubble_sort that sweeps the list, comparing elements
If it is sorted, end iteration. Otherwise, swap elements
The end starts at len(items)-1
In each iteration, subtract 1 from the end index

assert bubble_sort([8, 3, 5, 7, 1]) == [1, 3, 5, 7, 8]

Write bubble sort

Replace the two lines of comment with your code:

def bubble_sort(items):
  is_sorted = False
  end = len(items)-1
  while not is_sorted:
    # <---------> 
    for i in range(end):
      if items[i] > items[i+1]:
        items[i], items[i+1] = items[i+1], items[i]
        # <---------> 
    end -= 1

Write bubble sort – solution

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]

How many total sweeps and swaps to sort this list?

numbers = [ 3, 1, 7, 2, 4 ]

How many total sweeps and swaps?

[ 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?

numbers = [ 3, 1, 7, 2, 4, 8, 5 ]

How many sweeps, swaps? (part 1)

[ 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

How many sweeps, swaps? (part 2)

[ 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

How many total sweeps and swaps?

Go to gradescope and answer today’s attendance question:

numbers = [ 1, 5, 5, 7, 2, 4 ]

Lots of algorithms

There are many sorting algorithms
- Bogo sort
- Selection sort
- Bubble sort
- Insertion sort
- Merge sort
- Quick sort
- ...more...

Visualization

Flash Warning: the following video contains flashing lights. https://www.youtube.com/watch?v=kPRA0W1kECg

selection sort at 0:00, bubble sort at 4:00