News for hackers. Stuff that matters.

A comment on Strangest Sorting Algorithms. Parent comment

Re:Strangest Sorting Algorithms by mkbosmans on Tuesday March 01, 2022 @02:15AM (#30510702)
It is an overly strict interpretation of that rule to assume it prohibits any randomized algorithm.

Aren't these the same steps for any given input?

  1) Roll dice to get random number N
  2) Get the Nth permutation of the input sequence (for some ordering of permutations)
  3) Permute input sequence
  4) If sorted: done, else goto step 1
[ Parent | on HN ]
Re:Strangest Sorting Algorithms by olliej on Tuesday March 01, 2022 @03:12AM (#30511112)
You have to specify the output of rolling the die. If you use an RNG you would provide the seed state for the RNG as an input to the algorithm.

Think of it as “can I run this algorithm on a Turing machine”

[ Parent | on HN ]