sorting (class 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?

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?

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

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

Selection sort

Selection sort is a very simple sorting algorithm

  1. Scan the list and find the smallest element

  2. Swap this element with the beginning element

  3. Continue these steps for the remaining list, not including the element just swapped

  4. Repeat

Selection sort

Write selection sort - step 1

  1. Function name is find_min_index
  2. It takes a list of numbers as argument
  3. It iterates over the list, scanning the list to find the smallest number
  4. 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, 20, 1, 7, 9, 43, 10, 12]
  print(find_min_index(test_list)) # 3
  
main()
3

Write selection sort - step 1 continue

  1. Call your find_min_index function
  2. Find the smallest number starting from a specified index
  3. Return the index of that smallest number
begin_index = 3
items = [5, 10, 1, 20, 7, 3, 9]

print(items[begin_index:]) # [20, 7, 3, 9]

print(find_min_index(items[begin_index:])) # 2
print(find_min_index(items[begin_index:]) + begin_index) # 5

Write selection sort - step 2

  1. Function name is selection_sort
  2. It takes a list as argument
  3. It mutates the list argument, sorting it
  4. It iterates over the list, call find_min_index to find the index of smallest element
  5. It swaps the smallest element found in each iteration with the beginning element

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?

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

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?

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

Attendance

Go to gradescope and answer today’s attendance question

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

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

  1. Function name is single_sweep_swap
  2. It takes a list as argument
  3. It mutates the list, sorting it
  4. It iterates over the list, comparing each element with the next one, if the next one is smaller, swap elements
  5. 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

  1. Function name is bubble_sort
  2. It sweeps the list, comparing elements
  3. If it is sorted, return the list. Otherwise, swap elements
  4. It sweeps the list in a iteration. The end starts at len(items)-1
  5. 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 – 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 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?

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

Attendance

Go to gradescope and answer today’s attendance question

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

Lots of algorithms

  • There are many sorting algorithms

    • Bogo sort

    • Selection sort

    • Bubble sort

    • Insertion sort

    • Merge sort

    • Quick sort

    • ...more...

Visualization

https://www.youtube.com/watch?v=kPRA0W1kECg