Perl Monk, Perl Meditation | |
PerlMonks |
Re: sort behavior explanation requiredby davido (Cardinal) |
on Apr 20, 2014 at 16:13 UTC ( [id://1082950]=note: print w/replies, xml ) | Need Help?? |
In the first case you're doing stringwise comparisons (cmp does this), and the default behavior for those types of comparisons is ASCII or Code Point order. In the second case you are doing numeric comparisons. Perl happily obliges by trying to convert every string to a number. So you need to come to an understanding of how Perl converts strings to numbers. This is described in detail in perldata. But the simplest way to think about it is that a string that starts with numeric digits optionally preceded with a sign or decimal point will be converted to a non-zero number. Any other string will be converted to 0 (a small oversimplification, but reasonably close). So in your case, "jack", "martin", "allan", and "george" are all converted to the numeric value "0", while 80 and 3 are taken for their inherent values. That leaves only one question; what happens when several elements that all evaluate to numeric zero are sorted? Internally, modern Perls use a Merge Sort algorithm, which is a "stable stort." Stable sorts maintain original order of elements that have equal values. So your strings "jack", "martin", "allan", and "george" retain their original order. And since they all evaluate to zero, the actual non-zero numbers come after them. Perl hasn't always used the merge sort internally. Older Perl versions (5.6 and earlier, perhaps, but I don't remember for sure) used Quicksort. Quicksort had two disadvantages though. The first, and most commonly discussed is its propensity for going quadratic in computational time given some pathological inputs (O(n^2)), while still exhibiting an average case of O(n log n). Merge sort is guaranteed of a worst-case of O(n log n). But the other important difference (and disadvantage to QuickSort) is that it is not "stable", meaning that the order of equal-valued elements is not preserved. "jack", "martin", "allan", and "george" could end up in some other order, which is very difficult to predict ahead of time. The one advantage to Quicksort is that there is a little less work done on each iteration, so runtime on average can be a few cycles less. But that is usually so insignificant as to not really matter, and certainly not worth dealing with the downsides of possible O(n^2) time complexity for some data sets, and non-stable sorting of equivalent values. Dave
In Section
Seekers of Perl Wisdom
|
|