On Mon, Sep 15, 2014 at 8:50 PM, Asumu Takikawa <as...@ccs.neu.edu> wrote: > On 2014-09-15 18:57:51 -0700, Matthew Butterick wrote: >> Mike Bostock's visual demonstration of why naive sorting functions are false >> friends. As he and Henglein point out, transitivity of the comparator is >> essential. >> >> http://bost.ocks.org/mike/shuffle/compare.html > > Thanks, that's really interesting. Also means that our implementation of > `shuffle` in Racket stdlib is not great: > > (define (shuffle l) > (sort l < #:key (λ(_) (random)) #:cache-keys? #t)) > > (more prose on the algorithm here: > http://bost.ocks.org/mike/algorithms/#shuffling)
This is different than linked algorithm. This one assigns a random number from [0,1) to each element where the linked algorithm assigns a random pairwise ordering to each comparison. I don't think there is anything wrong from a correctness standpoint on the stdlib's algorithm. > > Cheers, > Asumu > ____________________ > Racket Users list: > http://lists.racket-lang.org/users ____________________ Racket Users list: http://lists.racket-lang.org/users
