erreon Hacker News • Recommends
On “A regular expression matcher By Rob Pike and Brian Kernighan (2007)”
Ah, and Jon Bentley's chapter about quicksort, along whose lines there's a (also very interesting) Google Tech Talk: link to this video
0:00 / 0:00
Three Beautiful Quicksorts
Google TechTalks
349K subscribers • 62 videos on Hallway
- Recommended by 2 people: 2 on Hacker News.
- A classic. People kept recommending it from 2013 to 2023.
- Presented by Jon Bentley, computer scientist
Intermediate. Assumes working knowledge.
45K views19 years ago2 recommendations
Computer scienceSoftware designAlgorithmsRefactoring and legacy codeSimplicity and complexity
Jon Bentley presents three implementations of the Quicksort algorithm, demonstrating how systematic code transformations can make programs simpler and more powerful.
Google Tech Talks August 9, 2007 ABSTRACT This talk describes three of the most beautiful pieces of code that I have ever written: three different implementations of Hoare's classic Quicksort algorithm. The first implementation is a bare-bones function in about a dozen lines of C. The second implementation starts by instrumenting the first program to measure its run time; a dozen systematic code transformations proceed to make it more and more powerful yet more and more simple, until it finally disappears in a puff of mathematical smoke. It therefore becomes the most beautiful program I never wrote. The third program is an industrial-strength C library Qsort function that I built with Doug...Why it's here
2 people recommend thisWhat people say. Recommended as an inspiring talk on code elegance, refactoring, and the beauty of deleting code to add function.
tonym128on Hacker News • Recommends
On “Ask HN: Where do I find good code to read?”
I'm sorry these are videos, but your question made me think of these. If you're looking for programming inspiration I love these videos Jon Bentley - Three Beautiful Quicksorts link to this video Bret Victor - Inventing on Principle link
u/hackingdreamsin r/compsci • Mentions
On “Why is quicksort better than other sorting algorithms in practice?”
It's worth a note that almost all n-lg-n sorts do this these days, including Quicksort. During the quicksort divide-and-conquer, if the size of the split array is < ~10, it just uses insertion sort to sort it.
Jon Bentley (yep, THAT Bentley, from Bell Labs) did a talk about Quicksort at Google where he discusses this and other optimizations used in modern implementations.
ehsanulon Hacker News • Mentions
On “-2000 Lines Of Code”
I'm reminded of this Google Tech Talk, where the speaker (Jon Bentley) refers to a colleague's praise of someone who "adds function by deleting code": link to this video Edit: Fixed quote