Raspberry Pi Learning Resources

Visualising Sorting With Python - Insertion Sort

In this lesson students will implement an insertion sort in Python and visualise its action using matplotlib.

Learning objectives

  • To understand the mechanics and performance of the insertion sort algorithm

Learning outcomes

All students are able to

  • Describe the basic mechanics of the insertion sort algorithm

Most students are able to

  • Implement an insertion sort in Python
  • Describe the mechanics of the insertion sort algorithm in detail

Some students are able to

  • Critically analyse the performance of the algorithm and identify its weaknesses

Lesson summary

  • Students use matplotlib to visualise a single element being sorted using the algorithm
  • Students implement the full sorting algorithm

Starter

  • Insertion sort can easily be visualised using a pack of cards

animation

  • Deal out a hand of 5 cards; if you have enough you could deal these out to the students, or to 10 groups at least
  • The card on the far left is ignored
  • The next card along is left in place if larger, or swapped if smaller
  • The next card along is then moved left until it reaches the correct place in the hand
  • This can be repeated two more times to order the hand

Main development

  • The students can work their way through the worksheet, slowly building up the insertion sort algorithm until it is complete.

Plenary

  • Have students compare the speed of their bubble sort and insertion sort algorithms
  • They can remove their display() function calls and provide the algorithms with very large lists - 5000 items should do

Extension

  • Have students research optimisation for the insertion sort algorithm