3 ms·
I feel like the sieve is a poor example, since it's not actually the same algorithm as a sieve, and has a worse running time. It is possible to write a very ni
by Tyr42 12y ago
I feel like the sieve is a poor example, since it's not actually the same algorithm as a sieve, and has a worse running time. It is possible to write a very nice lazy infinite sieve.
See O’Neill's "The Genuine Sieve of Eratosthenes" paper for details.
http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
- judk 12y agoIt fits the tradition established by the quicksort that isn't really a quicksort.
- axman6 12y agoThat example does match some high level definitions of quicksort; "pick a pivot element (the first element of the list), split the rest of the list into elements less than and greater than or equal to the pivot, quicksort those recursively, then reassemble the lesser, pivot and then greater elements". But I do agree it's not quicksort as it's usually known with its in place sorting and O(1) extra storage.