You are here

Striving for Efficiency in Algorithms: Sorting

Author(s): 
Inna Pivkina (New Mexico State University)

Introduction

   

 

Figure 1. C.A.R. (Tony) Hoare (left) in June of 2011, and Robert Sedgewick. (Sources: Wikimedia Commons, © Rama, Cc-by-sa-2.0-fr, and Coursera.org, respectively. Images used with permission of subjects Hoare and Sedgewick as well.)

Sorting is the fundamental algorithmic problem in computer science. It is the first step in solving many other algorithmic problems. Quicksort is a comparison sorting algorithm that is often faster in practice than other comparison sorting algorithms and it has some other advantages.

Figure 2. Quicksorting \(\pi\) ([1])

Quicksort was invented by British computer scientist C.A.R. (Tony) Hoare in 1960. After its invention by Hoare, Quicksort underwent extensive analysis by Robert Sedgewick in the 1970s. Sedgewick, in his 1978 paper “Implementing Quicksort programs” ([1]), presented step-by-step modifications to the algorithm, which made its implementation on real computers more efficient.

Programming in the 1970s was very different from programming now. Today, if you need to sort items, your best choice may be to use the system sort function. Compilers today often do a better job than people at optimizing the code. This was not the case in the 1970s. Back then, sorting was extremely important and good system sort functions had not been developed yet. Programmers of the era needed to be creative in order to make sorting more efficient. Sedgewick's contributions included techniques to eliminate recursion and to switch to a more elementary algorithm when the subarray under consideration was small enough, in addition to other steps described in his paper. Optimizations discussed in the paper made the code harder to understand, but Sedgewick found it necessary to complicate the code in order to make it more efficient.

The goal of the project is to study Quicksort and experimentally determine whether or not modifications to the Quicksort algorithm proposed by Sedgewick in [1] are still good today. Would they make any difference in sorting time today?

The project, Striving for Efficiency in Algorithms: Sorting, is ready for students, and the Latex source is also available for instructors who may wish to modify the project to better suit their needs. The “Notes to the Instructor” presented next are also appended to the project itself.

Our primary source project module for students is part of a larger collection published in Convergence. For more projects, see Primary Historical Sources in the Classroom: Discrete Mathematics and Computer Science.

Notes to the Instructor

The project is designed for a junior-level Data Structures and Algorithms course. It is based on the 1978 paper by Robert Sedgewick, “Implementing Quicksort Programs” ([1]). In the paper, Sedgewick presented “a practical study of how to implement the Quicksort sorting algorithm and its best variants on real computers.” The paper contains the original version of Quicksort and its modification, which, as Sedgewick said, combined the most effective improvements to Quicksort to date. The main idea of the current project is to experimentally verify whether modifications to the Quicksort algorithm proposed by Sedgewick would make any difference in sorting time today.

The project allows students to learn and practice Quicksort, insertion sort, recursive thinking, using implicit stack data structure to remove recursion, computing running times of algorithms, etc. It could also be used to illustrate how developments in computer architecture and computer technology have affected programming since the 1970s. When Sedgewick wrote the paper, compilers were unable to produce high-quality code and hand-optimization was important. Today the situation is reversed: compilers can often produce code that better exploits a specific architecture than people can.

The project is divided into two parts. The first part contains excerpts of Sedgewick’s paper ([1]) interleaved with exercises. The purpose of these exercises is to engage the reader with the algorithm and its optimizations discussed in the paper. The second part contains exercises guiding the reader to experimentally compare the original and modified versions of Quicksort. The first part (Sedgewick’s paper) can be split further into two segments which would contain approximately the same amount of reading from Sedgewick’s paper. The first segment could include the sections, “The Algorithm,” “Improvements,” “Removing Recursion,” and “Small Subfiles,” together with the related exercises. The second segment could include the sections, “Worst case,” “Median-of-three Modification,” and “Implementation,” together with the related exercises. The project can be given as a two- or three-part homework assignment. It can be completed individually or in small groups in about two weeks.

Download the project Striving for Efficiency in Algorithms: Sorting as a pdf file ready for classroom use.

Download the modifiable Latex source file for this project.

For more projects, see Primary Historical Sources in the Classroom: Discrete Mathematics and Computer Science.

Reference

[1] R. Sedgewick. Implementing Quicksort programs. Communications of the ACM, 21:847–857, 1978.

Acknowledgment

The development of curricular materials for discrete mathematics and computer science has been partially supported by the National Science Foundation’s Course, Curriculum and Laboratory Improvement Program under grants DUE-0717752 and DUE-0715392 for which the authors are most appreciative. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

Inna Pivkina (New Mexico State University), "Striving for Efficiency in Algorithms: Sorting," Convergence (July 2015)