Class11.md

Class 11: Iterative Sorting Algorithms

Topics

• Algorithm to check if items in a list are in sorted order
• Counting how many inversions there are in a list
• Classic iterative sorting algorithms: bubble sort, selection sort, insertion sort

Resources

• Play with VisuAlgo's interactive sorting visualizations including bubble, selection, and insertion sort
• Play with USF's interactive sorting animations including bubble, selection, insertion, and Shell sort
• Read Vaidehi Joshi's articles: an overview of sorting, bubble sort, selection sort, and insertion sort with beautiful drawings and excellent analysis
• Watch Zutopedia's insertion sort vs bubble sort robot video
• Watch Harvard's bubble sort video, selection sort video, and insertion sort video
• Watch HackerRank's bubble sort tutorial video (spoiler alert: contains solution code)
• Watch Toptal's sorting animations to see how algorithms compare based on input and read the discussion section
• Watch dancers perform bubble sort with Hungarian folk dance, selection sort with Gypsy folk dance, and insertion sort with Romanian folk dance
• Watch videos to observe patterns: 9 sorting algorithms, 15 sorting algorithms, 23 sorting algorithms
• Read Interview Cake's triangular series article for more background on counting inversions and pairs

Challenges

• Implement these classic iterative sorting functions using sorting starter code:
  • is_sorted(items) - return a boolean indicating whether all items are in ascending order
  • bubble_sort(items) - swap adjacent items that are out of order, repeat until all items are sorted
  • selection_sort(items) - find minimum item in unsorted items, swap it with first unsorted item, repeat until all items are sorted
  • insertion_sort(items) - take first unsorted item, insert it in sorted order in front of items, repeat until all items are sorted
• Run python sorting.py to test sorting algorithms on a small random sample:

  $ python sorting.py bubble_sort 10 20
  Initial items: [3, 15, 4, 7, 20, 6, 18, 11, 9, 7]
  Sorting items with bubble_sort(items)
  Sorted items:  [3, 4, 6, 7, 7, 9, 11, 15, 18, 20]
  

• Annotate functions with complexity analysis of running time (operations) and space (memory usage)
• Write a thorough suite of sorting unit tests to ensure your sorting algorithms are robust
  • Write tests in a way that lets you add new sorting functions without needing to write more tests
  • Include a variety of test cases that cover many different input types, orderings, distributions, and edge cases
• Run pytest sorting_test.py to run the sorting unit tests and fix any failures

Stretch Challenges

• Extend sorting algorithms with an order parameter to specify ascending or descending order
• Extend sorting algorithms with a key parameter to specify a function to call on each item when making comparisons (read about Python's sorted function and how to use key functions for more information)
• Implement an insertion sort variation using binary search to find the position to insert each item
• Implement improved iterative sorting algorithms: cocktail shaker sort, library sort, or Shell sort
• Annotate functions with complexity analysis of running time (operations) and space (memory usage)