My Quickshort interview with Sir Tony Hoare, the inventor of Quicksort
If you studied Computer Science, at some point, usually in the beginning of your algorithm courses, you learn about sorting algorithms, the most famous one being Quicksort. Studies show that the most frequent reactions to those who learn about Quicksort for the very first time are:
1) Wow!!! How could anyone possibly come up with that idea?
2) Hmm, explain it to me one more time please?
3) #1 followed by #2, or #2 follower by #1
Not surprisingly I was right there in the #3 category. To learn about Quicksort just Bing it, but this blog post isn't about Quicksort necessarily, but rather about the person who invented it, Sir Tony Hoare. The winner of the Turing Award prize in 1980, Sir Tony Hoare currently works at Microsoft, just like me, and he was kind enough to give me the honor to interview him for my coding blog. Without any further due, here it is - I hope you Quick-enjoy it too! :)
[Marcelo De Barros] First, thank you Tony for the incredible opportunity to ask you few questions! Let's start with the Quicksort: what’s your recollection of the day when you came up with the idea of the Quicksort? Can you walk us through how you came up with that idea?
[Sir Tony Hoare] I remember it clearly. In 1960, I was lounging on my bed/settee in my room in Moscow State University, thinking how I would write a program (in Mercury Autocode, the only programming language I knew) to sort words of a Russian sentence prior to looking them up in a Russian-English dictionary, which was held in alphabetic order on magnetic tape. Thus all the relevant entries for the whole sentence could be pulled off the tape in a single scan.
The first Idea I had was insertion sort, but I recognized that this a bit slow (quadratic). My second idea was quicksort. It occurred to me just as quickly as the first idea. I wrote the program for the partition, but I couldn’t write the program to account for the list of unsorted segments.
On return to England, I got a job with a small computer manufacturer. My first task was to write program the Shellsort algorithm, an in-situ sort that had recently been published. On completion of this task, I timidly told my boss that I thought I knew of a faster method. He bet me sixpence that I did not. He soon agreed that he had lost his bet.
Later, I discovered recursion from my reading of the Report on the ALGOL language. This enabled me to publish the program in algorithms section of the ACM
[Marcelo De Barros] So, did you manage to learn Russian after all? :)
[Sir Tony Hoare] I learnt Russian full-time on National Service in the Royal Navy, and qualified as an Interpreter.
[Marcelo De Barros] Did you know at the time that Quicksort was going to be a major breakthrough in Computer Science?
[Sir Tony Hoare] I knew that my algorithm was n log n, same as Mergesort, but better because it could sort twice the number of items in main memory. The innermost loop was also fast. I later did some math that showed and exact formula for the average running time, and published a paper in the British computer Journal.
Since I did not have any postgraduate degree, it was very lucky that I discovered quicksort. I gather now that another algorithm (Timsort?) is faster when sorting vast lists that are already nearly sorted.
[Marcelo De Barros] What is it like to work for Microsoft? :)
[Sir Tony Hoare] I’ve had a great fifteen years. Recently I have discovered the basic mathematical laws for Concurrent Programming, and achieved a unification of many previous theories about it.
[Marcelo De Barros] You know, this is a coding blog and as such I must write some code towards the end of every post, but this time around I'll pass the token to you to write some code - any code! :) Would you please?
[Sir Tony Hoare] I code in mathematics, so my snippet is a fundamental algebraic law which governs the interaction between concurrency || and sequentially (;) in computer programs:
(p||q) ; (p’||q’) < (p;p’) || (q;q’)
It’s not a new law, but it is ubiquitous and pervasive.
Thank you very much, Tony! And thanks to all the readers too - I'll see you next time!
Cheers,
Marcelo
1) Wow!!! How could anyone possibly come up with that idea?
2) Hmm, explain it to me one more time please?
3) #1 followed by #2, or #2 follower by #1
Not surprisingly I was right there in the #3 category. To learn about Quicksort just Bing it, but this blog post isn't about Quicksort necessarily, but rather about the person who invented it, Sir Tony Hoare. The winner of the Turing Award prize in 1980, Sir Tony Hoare currently works at Microsoft, just like me, and he was kind enough to give me the honor to interview him for my coding blog. Without any further due, here it is - I hope you Quick-enjoy it too! :)
[Marcelo De Barros] First, thank you Tony for the incredible opportunity to ask you few questions! Let's start with the Quicksort: what’s your recollection of the day when you came up with the idea of the Quicksort? Can you walk us through how you came up with that idea?
[Sir Tony Hoare] I remember it clearly. In 1960, I was lounging on my bed/settee in my room in Moscow State University, thinking how I would write a program (in Mercury Autocode, the only programming language I knew) to sort words of a Russian sentence prior to looking them up in a Russian-English dictionary, which was held in alphabetic order on magnetic tape. Thus all the relevant entries for the whole sentence could be pulled off the tape in a single scan.
The first Idea I had was insertion sort, but I recognized that this a bit slow (quadratic). My second idea was quicksort. It occurred to me just as quickly as the first idea. I wrote the program for the partition, but I couldn’t write the program to account for the list of unsorted segments.
On return to England, I got a job with a small computer manufacturer. My first task was to write program the Shellsort algorithm, an in-situ sort that had recently been published. On completion of this task, I timidly told my boss that I thought I knew of a faster method. He bet me sixpence that I did not. He soon agreed that he had lost his bet.
Later, I discovered recursion from my reading of the Report on the ALGOL language. This enabled me to publish the program in algorithms section of the ACM
[Marcelo De Barros] So, did you manage to learn Russian after all? :)
[Sir Tony Hoare] I learnt Russian full-time on National Service in the Royal Navy, and qualified as an Interpreter.
[Marcelo De Barros] Did you know at the time that Quicksort was going to be a major breakthrough in Computer Science?
[Sir Tony Hoare] I knew that my algorithm was n log n, same as Mergesort, but better because it could sort twice the number of items in main memory. The innermost loop was also fast. I later did some math that showed and exact formula for the average running time, and published a paper in the British computer Journal.
Since I did not have any postgraduate degree, it was very lucky that I discovered quicksort. I gather now that another algorithm (Timsort?) is faster when sorting vast lists that are already nearly sorted.
[Marcelo De Barros] What is it like to work for Microsoft? :)
[Sir Tony Hoare] I’ve had a great fifteen years. Recently I have discovered the basic mathematical laws for Concurrent Programming, and achieved a unification of many previous theories about it.
[Marcelo De Barros] You know, this is a coding blog and as such I must write some code towards the end of every post, but this time around I'll pass the token to you to write some code - any code! :) Would you please?
[Sir Tony Hoare] I code in mathematics, so my snippet is a fundamental algebraic law which governs the interaction between concurrency || and sequentially (;) in computer programs:
(p||q) ; (p’||q’) < (p;p’) || (q;q’)
It’s not a new law, but it is ubiquitous and pervasive.
Thank you very much, Tony! And thanks to all the readers too - I'll see you next time!
Cheers,
Marcelo
Comments
Congratulations Marcelo with interviewing a real legend! Considering significant percentage of CPU cycles spent on sorting, it's not an exaggeration to say that Sir Tony Hoare not only inspired generations of computer scientists (including me), but also made an outstanding contribution in saving nature by reducing amount of resources powering our busy CPUs.
Reply DeleteI remember back in university I was reading about Hoare logic and feeling for the first time that programming is an actual science with formal methods to reason about the code, and not just writing a random set of characters in a hope that it produces a desired output. It takes a touch of a genius to express profound ideas from parallel and distributed (which is fundamentally pretty much the same as parallel) programming in such a concise and elegant expression as: (p||q) ; (p’||q’) < (p;p’) || (q;q’)
It's true that some of the popular libraries and frameworks switched to Timsort, but it's implementation is trickier, which most likely contributed to introduction of only recently discovered bug in its Android Java and Python implementation (http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it). Personally I find QuickSort much more elegant and, well, quick in practice, so only after a careful performance benchmarks on common data patterns I work with, would I consider to move to any other algorithm for sorting.
Thank you very much Sir Tony for your hard and inspiring work!
Well, Marcelo, now that you set the bar so high, I hope some day you'll also interview another legend and superhero - Leslie Lamport.
Thank you and have a marvelous rest of the weekend!
Post a Comment
[γγ¬γΌγ ]