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.
- Sorting Algorithms
- Italian Language Version
- French Language Version
- Turkish Language Version
- Greek Language Version
- Portugese (Brazil) Language Version
- Polish Language Version
- Hungarian Language Version
- Slovenian Language Translation
- National Center for Women & Information Technology (NCWIT) has a learning package called Unplugged in a Box which has detailed lesson plan of the “Lighest and Heaviest” activity.
- 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.
- 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 .
- 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.
- Wikipedia: Sorting Algorithm
- The Mathmaniacs website has a related activity (lesson 8)
- 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.
- Soring Algorithms Applet some of which are developed and maintained by Jason Harrison at the University of British Columbia.
- 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/.
- Sorting Algorithm Animation System (SAAS) features a very clear comparison of sort algorithms using animation at http://www.mundayweb.com/html/Sorting%20Alogrithm%20Animation%20System%20(SAAS).html.
This animation can also be downloaded for offline use at any time.
- 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/.
- A good site that explains sort algorithms and also lets you do the sort yourself with instructions on each step of the algorithm is at http//mathsite.math.berkeley.edu/sorting/brick.html. Students can use this site to get guided on sort algorithms step-by-step.
- American Scientist has an article called Trains of Thought by Bryan Hayes. This article has interesting puzzles based on sorting railway wagons.
- 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.
- 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
- Fachhochschule Flensburg has a pagededicated to sequential and parallel sorting algorithms at Sequential and parallel sorting algorithms.
See in particular the Sorting Contest that compares some sort algorithms.
- Hiroki Manabe has programmed Bubble Sort and Insertion Sort using animation in Alice IDE at locations below:
- Virginia Tech, Dept of Computer Science has a complete module on Algorithms. See the lessons that relate to Sorting Algorithms below:
- R Mukundan from University of Canterbury has applets to demonstrate the following sort techniques:
- Showsort has visualisations of a complete set of algorithms from bubble sort to tree sort. This application presents a graphical representation of sorting an array of integers. In addition to the animated sorting, this app includes a description of each sorting algorithm with the source code. Note: This applet is not recommended for Internet Explorer.
- Herong Yang‘s Herong’s Tutorial Notes on Sorting offers a good explanation to beginners in Bubble Sort, Heap Sort, Insertion Sort, Merge Sort, Quicksort, Selection Sort, and Shell Sort.
- 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.
- 2 July Maths UK website for Mathematics has some useful resources in algorithms and their development:
- BBC h2g2 has some articles on algorithms below:
- Kamal at RawKam has the following posts on the Towers of Hanoi problem:
- Towers of Hanoi
- Binary solution to Tower Of Hanoi
- Jeremy Kubica‘s Computational Fairy Tales has the following fairy tales/stories that explain the sorting algorithms below:
- Getting Sorted – Computerphile
- Quick Sort – Computerphile
- Programming BASIC and Sorting – Computerphile
Great Principles of Computer Science [info]
ACM K12 Curriculum [info]Expand
- Level I (Grades 35) 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.
New Zealand Curriculum [info]Expand
- Technology Level 1: Brief Development
- Describe the outcome they are developing and identify the attributes it should have, taking account of the need or opportunity
- Technology Level 1: Outcome Development and Evaluation
- Investigate a context to communicate potential outcomes. Evaluate these against attributes; select and develop an outcome.
- Technology Level 1: Planning for Practice
- Outline a general plan to support the development of an outcome, identifying appropriate steps and resources