[racket] Looking for feedback on code style

From: Will M. Farr (wmfarr at gmail.com)
Date: Thu Sep 9 12:15:25 EDT 2010

I should note that the code I posted also used randomness to select the pivot element, so the statements below apply to it, too.  It's on average O(N) (where average can mean either "run many times on the same input" or "run on many inputs of length N").

Will

On Sep 9, 2010, at 11:03 AM, Prabhakar Ragde wrote:

> On 9/9/10 11:33 AM, Phil Bewig wrote:
>> http://programmingpraxis.com/2009/12/11/selection/
> 
> This method takes O(n) time with high probability if the partitioning element is chosen deterministically and the data is randomly permuted (with all permutations equally likely) or if the partitioning element is chosen uniformly at random. Its deterministic worst-case cost is O(n^2). However, for a site called "Programming Praxis", it's definitely the right choice.
> 
> Our attitude towards randomness in computer science is a bit strange. I'm convinced most of our students graduate thinking that Quicksort is an O(n log n) algorithm, but this is only true in a probabilistic model. On the other hand, the shortest, cleanest, and most elegant method I know of to balance binary search trees (which underlies non-hash efficient set and map implementations) uses randomness, but no one talks about it or knows it. --PR
> _________________________________________________
> For list-related administrative tasks:
> http://lists.racket-lang.org/listinfo/users



Posted on the users mailing list.