Date: 14 Mar 2012
From: jyrki@diku.dk
Subject: Didactics talk: Teaching sorting algorithms

Guest talk: Sorting algorithms as special cases of a priority-queue sort
Speaker: Bengt Aspvall, Blekinge Institute of Technology
Time: Wednesday, 21 March 2012 at 14.05–15.00
Place: Little Auditorium (Universitetsparken 1)

Abstract:

This paper offers an exercise for revisiting the main sorting
algorithms after they have been taught to students. This is done in a
way that emphasizes the relationships between them, and shows how
considering abstraction and extreme cases can lead to the generation
of new algorithms. A number of authors (including textbook authors)
have noted particular relationships between algorithms, such as an
uneven split in merge sort being equivalent to insertion sort. In this
paper we use a flexible priority queue, the d-heap, to derive three
common sorting algorithms. We combine this with using a binary
search tree as a priority queue, plus prior observations in the
literature, to show strong relationships between the main sorting
algorithms that appear in textbooks. In the process students are able
to revisit a number of algorithms and data structures and explore
elegant relationships between them. This approach can also lead to
exercises and exam questions that go beyond desk-checking to evaluate
students' understanding of these algorithms.

(Joint work with Tim Bell)

Bengt's home page: http://www.ide.se/~bia/
PE-lab's home page: http://www.diku.dk/~jyrki/PE-lab/