Re: sort function and parity of the permutation.

If by "parity of the permutation" you mean the number of elements out of place (or whether that number is even or odd, or the sum of the counts of elements that are on the wrong side of an element over all elements), then I think it's not possible. As Perl uses quicksort as its sorting algorithm, and that sorting algorithm swaps elements across large distances, you can't keep track of the parity in its callback.

You can maybe look at the implementation and infer that Perl will always call the sort block with $a being the left element and $b being the right element in the sequence. But then determining a parity from the number of calls your callback receives and the elements that get compared still strikes me as fragile if even possible at all.

Comment on Re: sort function and parity of the permutation. Select or Download Code

Replies are listed 'Best First'.
Re^2: sort function and parity of the permutation. by JavaFan (Canon) on Feb 14, 2011 at 10:13 UTC
As Perl uses quicksort as its sorting algorithm, and that sorting algorithm swaps elements across large distances, Oh, please, ditch your 5.6, and enter the 21st century. `;-)`. As of 5.8, Perl uses an implementation of mergesort as its default sorting algorithm.	[reply]
Re^3: sort function and parity of the permutation. by Anonymous Monk on Feb 14, 2011 at 10:26 UTC
sort `use sort 'stable'; # guarantee stability use sort '_quicksort'; # use a quicksort algorithm use sort '_mergesort'; # use a mergesort algorithm use sort 'defaults'; # revert to default behavior no sort 'stable'; # stability not important use sort '_qsort'; # alias for quicksort` [download]	[reply] [d/l]
Re^2: sort function and parity of the permutation. by LanX (Saint) on Feb 15, 2011 at 10:52 UTC
I think it's about the sign function sgn(σ) of permutations, which tells the parity of necessary transpositions (swapping just two elements) IMHO it should be simple to reproduce and count these transpositions by comparing input and output of the sorting so it's O(n). Faint memories tell me that counting the numbers of elements which need to be "pushed forward" is already enough.š Cheers Rolf š) Never mind, this was wrong! For {4,3,2,1} it's even and for {4,3,1,2} it's odd.	[reply]