Tony Hoare, the inventor of Quicksort, in 2011. Photo: Rama, CC BY-SA 2.0 FR
There aren't many computer algorithms famous enough to get their very own birthday party, but Quicksort is one of them. Invented by the computer scientist Tony Hoare and published in July 1961, the algorithm's task is to put lists of things into the correct order: numbers in numerical order, words into alphabetical order, or dates into chronological oder. It does this so successfully, it is still hailed as one of the best sorting algorithms and implemented in many programming languages and libraries.
The following articles explore the invention of Quicksort, how it works, and some other aspects of Tony Hoare's work. They are based on a conversation we had with Hoare, who is currently participating in a workshop run by the Isaac Newton Institute for Mathematical Sciences in Cambridge, as well as a talk he gave there. Enjoy!
Starting with bubbles — Hoare tells us how Quicksort started with an idea he had while lying on a sofa, which involved bubbles.
Happy birthday Quicksort! — We explore the famous algorithm itself with lots if intuition and no computer code.
Tony Hoare: Beyond Quicksort — A quick look at some of Hoare's work towards a beautiful new world where computer errors are a thing of the past.
The Verified Software Initiative — In this video talk on the website of the Isaac Newton Institute Hoare talks about his work on making error-free software a reality.
This content is part of our collaboration with the Isaac Newton Institute for Mathematical Sciences (INI), an international research centre and our neighbour here on the University of Cambridge's maths campus. INI attracts leading mathematical scientists from all over the world, and is open to all. Visit www.newton.ac.uk to find out more.
