in reply to Re: Fast way to check if a sort was doen
in thread Fast way to check if a sort was doen

I believe this would still be O(2n). Even if Digest::MD5::md5 is really written in C, so it might be FASTER, but it's the same amount of work. i.e. you are still running through each element of both arrays.
  • Comment on Re^2: Fast way to check if a sort was doen

Replies are listed 'Best First'.
Re^3: Fast way to check if a sort was doen
by Outaspace (Scribe) on Jun 28, 2007 at 16:11 UTC
    But I think it is the fastest way. If I would test for a change in the sort sub, there would be maybe more comparisons. I think I use this because it also works for "reverse sort @array".

    Thanks,
    Andre
[reply]
      Outaspace,
      Depending on how you interpret your question, the solution can be done in worst case O(N). If the only thing that is desired is knowing if sorting the array will change the order, then the algorithm is simple.

      Walk the original array testing if each element is in the position it is supposed to be (same as your sort block). If you get to the end, your array is already sorted and there is no need to sort it. If you find an element out of order than you know the array needs to be sorted (which will change the order).

      The trick is that you can't actually both know that the array needs to be sorted and sort it in better than O(N). At least I couldn't think of a way in the 2 minutes I spent thinking about it.

      Cheers - L~R

[reply]

In Section Seekers of Perl Wisdom