Striving for Efficiency in Algorithms: Sorting

Abstract

Sorting is the fundamental algorithmic problem in computer science. It is the first step in solving many other algorithmic problems. Quicksort, invented in 1960 by British computer scientist C.A.R (Tony) Hoare, is a comparison sorting algorithm that is often faster in practice than others. In the 1970s, Quicksort underwent extensive analysis by Rober Sedgewick. who, in his 1978 paper “Implementing Quicksort programs,” presented step-by-step modifications to the algorithm, which made its implementation on real computers more efficient. In this project, students will study Quicksort and experimentally verify whether modifications to the Quicksort algorithm proposed by Sedgewick would make any difference in sorting time today. The project is designed for a junior-level Data Structures and Algorithms course.