Sorting Algorithms

Lightest and Heaviest #

Almost any list that comes out of a computer is sorted into some sort of order, and there are many more sorted lists inside computers that the user doesn’t see. Many clever algorithms have been devised for putting values into order efficiently.

In this activity students compare different algorithms to sort weights in order.

Activity description (PDF) #

• Instructions for Sorting Algorithms activity (English)

Translations and other versions #

• Arabic language version
• Chinese language version
• French language version
• German language version
• Greek language version
• Hungarian language version
• Italian language version
• Polish language version
• Portuguese (Brazil) language version
• Slovenian Language Translation
• Turkish language version

Videos #

See our video page.

Photos #

Related Resources #

An older version of this activity can be downloaded in PDF format here. The content is similar to the current version, but there’s some extra technical information.

More lessons and activities #

• Misha Leder, a Software Engineer at Google has an activity called Sorting that looks at what sorting is, what it is for, by what criteria can one sort things, and different sorting algorithms (selection, insertion and bubble sort). Have kids sort themselves and time them.
• Try the Weighing Balls Puzzle by Jo Edkins
• A nice extension to this module is a Kinaesthetic Learning Activity (KLA) activity developed by Paul A. G. Sivilotti to introduce CS concepts to high school girls is Parallel Programming: “Parallel Programs are Fast”. This activity compares sort algorithms such as Bubble Sort , Even-Odd Transposition Sort and Radix Sort.
• Rutgers University Computer Science Department has an analysis book shelving activity to get students to develop a sort algorithm to shelve books in a library, and calculate the cost to sort books using the algorithm.
• The Royal Institution UK and Microsoft Research together have produced activities in sorting algorithms for the classroom at Get it Sorted .
• The Mathmaniacs website has a related activity (lesson 8)
• Several Java Applets that can be used to demonstrate different sort algorithms are collated by Henry can be viewed at http://home.westman.wave.ca/~rhenry/sort/.
• Jeremy Kubica’s Computational Fairy Tales has the following fairy tales/stories that explain the sorting algorithms below:
  • Why Tailors Use Insertion Sort
  • Bullies, Bubble Sort, and Soccer Tickets

Sorting algorithms visualisations #

• To visually demonstrate the concept of  some popular algorithms for sorting data, see the following website developed by David Martin at http://www.sorting-algorithms.com/.
• Aldo Cortesi’s Canvas visualisation of algorithms is another way to visualise sorting algorithms by Jacob Seidelin at Canvas Visualizations of Sorting Algorithms Teachers could print these out for different search parameters for different sort algorithms and hang these canvases as posters in the classroom. These could then be used in quizzing the students on specific algorithms or comparing sorts side by side. See also Cortesi’s Blog at Visualising Sorting Algorithms
• Another visual or timed view of sorting algorithms developed by David Eck can be seen at The xSortLab Applet.
• Thomas Baudel has visualisations of sort algorithms at Sort Algorithms Visualizer

If you want to find out more #

• Wikipedia: Sorting Algorithm
• Fachhochschule Flensburg has a page dedicated to sequential and parallel sorting algorithms at Sequential and parallel sorting algorithms.
• Virginia Tech, Dept of Computer Science has a complete module on Algorithms. See the lessons that relate to Sorting Algorithms below:
  • Sorting Algorithms
  • Basic Operations
  • Simple Card Sort
  • Simple Sort
  • Insertion Card Sort
  • Insertion Sort
  • Selection Card Sort
  • Selection Sort
• A famous story about the boy wonder of mathematics has taken on a life of its own. American Scientist has an article called Gauss’s Day of Reckoning by Bryan Hayes. The number of comparisons made for the simple sorting methods can be calculated using the sum 1+2+3+…+n-1, which is equal to n(n-1)/2. This series is often associated with stories of the mathematician. Gauss, who apparently used this equality to frustrate a teacher who had assigned the class to add up all the numbers from 1 to 100. There’s a wonderful article about whether or not this story is apocryphal.
• BBC h2g2 has some articles on algorithms below:
  • Algorithms
  • Basic Sorting Algorithms
  • Packing Algorithms

Videos #

• Michele Fini from Italy does a Bubble Sort activity with her 11 and 12 year olds class in the following Video: Bubble Sort (Ordinamento singolo)
• The following videos are in sorting using Unplugged Video: Quicksort by Cards and Video: Watch Aaron H doing Quicksort on a stack of graded homeworks
• There are many excellent visualizations of sorting algorithms available on the web. This is the classic video for every computer science student made in the 80’s by Dr. Ronald Baecker from University of Toronto at Video: Sorting out Sorting
• MIT Open Courseware in Electrical Engineering and Computer Science has the following lecture Video: Lecture 9: Binary Search, Bubble and Selection Sorts by Eric Grimson and John Guttag.
• Getting Sorted – Computerphile -Quick Sort – Computerphile -Programming BASIC and Sorting – Computerphile

Additional resources #

• Mordechai (Moti) Ben-Ari from the Weizmann Institute of Science, Israel has programmed quick sort and selection sort algorithms in Scratch which can be downloaded in a zip file of the complete set of activities. Please read the ReadMe.txt for documentation.
• Sorting Algorithm Animation System (SAAS) features a very clear comparison of sort algorithms using animation. This animation can also be downloaded for offline use at any time.
• Mr Barton Maths has a great resource called Sorting Algorithms, which is an impressive spreadsheet which covers bubble sort, shuttle sort, and other sorting algorithms. the original list of numbers can be edited to suit your needs.

Curriculum Links #

Great Principles of Computer Science #

• Computation

ACM K12 Curriculum #

• Level I (Grades 3–5) Topic 11: develop a simple understanding of an algorithm
• Level I (Grades K-12) Topic 12: Understand how to arrange (sort) information into useful order, such as a telephone directory.