Séminaire du 6 octobre 03, Conrado Martínez

Forty years of Quicksort and Quickselect: a personal view

Since their inception in the early sixties by C.A.R. Hoare, quicksort and quickselect are among the dozen or so most fundamental algorithms in computer science. Being primary and highly successful examples of divide-and-conquer design principle, these two algorithms combine beauty, efficiency, simplicity and practicality to provide solution to two basic problems: sorting and selection. They also rank among the most carefully analyzed algorithms ever, yet after four decades of deep study they still pose amazing and interesting mathematical challenges.

In this talk, I will briefly summarize some of the research efforts conducted on quicksort and quickselect, and I will present some new contributions to the understanding of these two important algorithms.