Re: Fast way to check if a sort was doen

Replies are listed 'Best First'.
Re^2: Fast way to check if a sort was doen by whereiskurt (Friar) on Jun 28, 2007 at 16:08 UTC
I like this sentiment. Basically, you iterate the array until you find the first unsorted element (in this case it's the first item), and then trigger the sort. If you don't want to do that, then use a flag that is set any time the array is sorted. Some sanity could be gained if all items were only ever added to either the top XOR the bottom of the array. My final thought is perhaps you should use a sort like the 'Insertion Sort'. It will, on the average cases, deal with already sorted arrays at O(N). Good luck! Kurt	[reply]
Re^2: Fast way to check if a sort was doen by dsheroh (Monsignor) on Jun 28, 2007 at 16:37 UTC
My read of the original question is that he's not asking "how do I tell if the array has been sorted yet?" but rather "I just sorted an array; how can I tell whether the order was changed?" Inserting a non-sorted element doesn't really apply to the question that I think was asked, other than by providing the trivial answer of "you now know that it was changed because you deliberately made it unsorted first". As for an actual answer, that'd take some benchmarking of different detection methods to be sure what's fastest, but my money's on the MD5 solution, especially for large arrays.	[reply]
Re^2: Fast way to check if a sort was doen by Outaspace (Scribe) on Jun 28, 2007 at 16:05 UTC
This would only work with "sort @array" but not with "reverse sort @array"	[reply]
Re^2: Fast way to check if a sort was doen by clinton (Priest) on Jun 28, 2007 at 16:21 UTC
hmmmm `my @array = qw( Zygoma Zebra Zulu );` [download]	[reply] [d/l]
Re^3: Fast way to check if a sort was doen by halley (Prior) on Jun 28, 2007 at 16:48 UTC
I was going to argue and say that you shouldn't be overliteral. Obviously you can translate what he said to "insert some identifiable token". It doesn't matter what the sentinel token is, but selecting one does require a bit of knowledge of the input domain or the input set. In general, though, I'll assume that you meant that in the spirit of saying that there's no a priori way to verify a sorted set that's faster than O(n), and that there's no sentinel token value that exists which would be useful for in all possible input domains using a posteriori validation. -- `[ e d @ h a l l e y . c c ]`	[reply]