A permutation p₁,p₂,...,p_n of 1,2,...,n is even (resp. odd) if it can be returned to the original order 1,2,...,n using an even (resp. odd) number of interchanges of pairs of elements. It is known that every permutation is either even or odd (and therefore not both).

The sign, or signum (for those who want to be fancy), of a permutation is +1 for an even permutation and -1 for an odd permutation.

You are given the integer n and the array p initialized to the integer values p[1]=p₁, p[2]=p₂, ..., p[n]=p_n which are guaranteed to be a permutation of 1,2,...,n. What algorithm would you advocate for determining the sign of the permutation? You need not preserve the original contents of p.

(In reply to Solution by Bractals)

While Bractals' algorithm is indeed not a generalized sort, it does, under the given circumstances sort p into ascending order.  In doing so, it also is indeed more efficient than the Quicksort.  I've implemented both the quicksort method, while counting swaps, as well as Bractals' method, while counting changes of sign of SIGNUM with its two assignments, and indeed the number of sign changes of SIGNUM is less than the number of interchanges in the quicksort.

The program:

DECLARE FUNCTION bractals! (a!())
DECLARE SUB sort (a!(), first!, last!)
CLEAR , , 25000
CLS
DIM SHARED ct

DO
 n = INT(20 + RND(1) * 5)
 REDIM p(n)
 REDIM p2(n)
 FOR i = 1 TO n
  DO
   s = INT(RND(1) * n + 1)
  LOOP UNTIL p(s) = 0
  p(s) = i
  p2(s) = i
 NEXT
 FOR i = 1 TO n
   PRINT USING "###"; p(i);
 NEXT
 PRINT
 ct = 0
 sort p(), 1, n
 PRINT ct, SGN(.5 - (ct MOD 2))
 FOR i = 1 TO n
   PRINT USING "###"; p(i);
 NEXT
 PRINT
 ct = 0
 signum = bractals(p2())
 PRINT ct, signum
 FOR i = 1 TO n
   PRINT USING "###"; p2(i);
 NEXT
 PRINT
 PRINT
 DO: LOOP UNTIL INKEY$ > ""
LOOP

FUNCTION bractals (a())
 i = 1
 signum = 1
 n = UBOUND(a)
 DO WHILE i < n
   j = a(i)
   IF j = i THEN
    i = i + 1
   ELSE
    signum = -signum
    a(i) = a(j)
    a(j) = j
    ct = ct + 1
   END IF
 LOOP
 bractals = signum
END FUNCTION

SUB sort (a(), first, last)
  midV = (a(first) + a(last)) / 2
  p1 = first: p2 = last
  DO
    DO UNTIL (a(p1) > midV OR p1 = p2)
     p1 = p1 + 1
    LOOP
    DO UNTIL (a(p2) < midV OR p1 = p2)
     p2 = p2 - 1
    LOOP
    IF p2 > p1 THEN SWAP a(p1), a(p2): ct = ct + 1
  LOOP UNTIL p1 = p2
  IF a(p1) >= midV THEN p1 = p1 - 1
  IF a(p2) <= midV THEN p2 = p2 + 1
  IF p1 > first THEN sort a(), first, p1
  IF p2 < last THEN sort a(), p2, last
END SUB

The results:

Here the first row is a randomly sorted array of 20 to 25 members. The second row in each group is the number of swaps the quicksort used, and its concommitant value for the sign. The third line in each group verifies that the array has been sorted. The population of array p was simultaneously made to p2, which Bractals' algorithm worked on.  The fourth line shows how many times the ELSE was taken in that algorithm, with its assignments, and the resulting SIGNUM. The fifth, last line in each group, shows the array p2 after Bractals' algorithm, and it is indeed sorted, as mentioned due to the special nature of the contents of the array.  In all instances, Bractals' algorithm took fewer ELSE's than the quicksort took swaps, and the results agree.

  5  8 19 20 22 17  3 21 11  9 15 23  1  2 16 18  7  4  6 10 13 14 12
 25           -1
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
 19           -1
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

 16  5 12  7 17  4 21  2  3 18  1  9 20  8 11 19 14 13 15 22 10  6
 28            1
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
 18            1
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22

  5  9  4 19 10  3  1  6 22 17 23  8 15 12 16  2 20 13  7 11 21 14 18
 27           -1
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
 21           -1
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

 13  9 12  5  7 18 19 10 17 11 14 15  3  1  2  4  6 20 16  8
 24            1
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
 18            1
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20

  6 21  1  7 13 18  9 15  5 17 12  8 20 19 10  4 16  3 11 14  2 22
 22            1
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
 18            1
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22

 21  8  2 19 14  7 18 11 12  9 16 13  5  4 20 10 17 15  6  1  3
 23           -1
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21
 19           -1
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21

  7 17  6  5  9 12  1 14  8 15 21 16 11 22 20 19  2 13  4  3 18 10
 26            1
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
 18            1
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22

 14  4 21 12 18 13 15 17  6  7  1  5 11 19  8 16  2 20  3  9 10
 29           -1
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21
 19           -1
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21

Posted by Charlie on 2006-08-05 17:24:50