Sorting Algorithms
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.
-
Typical equipment for the Sorting Algorithms activity
-
Mr. Nakamura explains sorting activity, Informatics Education Symposium 2010, Osaka, Japan
-
Mr. Idosaka and Prof. Kuno at a card sorting contest, Informatics Education Symposium 2010, Osaka, Japan
-
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. .
-
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.
-
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 .
-
Soring Algorithms Applet developed for the course Programming and Data Structures at the Linköpings universitet .
-
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/progs/applets/saas/.
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.
-
A really cool way to visualise algorithms is using different sound frequencies that need ordering or sorting, an idea by Ryan Compton at Musical Sorting Algorithms .
-
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. -
Insertion Sort is demonstrated using animation in Alice IDE at Insertion Sort on Alice by Hiroki Manabe .
-
Bubble Sort is demonstrated using animation in Alice IDE at Bubble Sort on Alice by Hiroki Manabe .
-
Virginia Tech, Dept of Computer Science has a complete module on Algorithms . See the lessons that relate to Sorting Algorithms below:
-
The Royal Institution UK and Microsoft Research together have produced activities in sorting algorithms for the classroom at Get it Sorted .
-
Barbara Ryder at 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.
-
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.