Sir Charles Antony Richard Hoare’s achiement which led to fame was his invention of the Quicksort algorithm in 1960.
He received an offer to work on a new project for machine translation from Russian to English while at the Moscow State University. But, because dictionaries were stored on magnetic tape, he would have needed to sort the words of a sentence into alphabetical order before translation.
Unfortunately the only programming language he knew at the time was Mercury Autocode which didn’t support recursion. When he later took a course in 1961 to study ALGOL 60 he noticed it’s capability of recursion. As part of his coursework he submitted the first draft of a new ultra-fast sorting mechanism to become known as quicksort.
Hoare also developed Hoare logic to verify program correctness, and the formal language Communicating Sequential Processes (CSP) to specify the interactions of concurrent processes (including the dining philosophers problem) and the inspiration for the occam, limbo & Go programming languages.
- Hoare also introduced the “null reference” in ALGOL W. Although NIL had existed in Lisp since 1959. In 2009 Hoare called this a “billion-dollar mistake”: I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn’t resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years. In recent years, a number of program analysers like PREfix and PREfast in Microsoft have been used to check references, and give warnings if there is a risk they may be non-null. More recent programming languages like Spec# have introduced declarations for non-null references. This is the solution, which I rejected in 1965.”
- The video below shows a visual demonstration of Quicksort in action using Hungarian folk dance.