3

std::sort (and related) is one of the crown jewels of the STL. However, when I try to use it in the context of numerical linear algebra, I find a glaring problem with it, which prevents me from using it.

The key is that in mathematics, keeping track of the parity (even/odd) of a permutation is usually relevant.

I can think of 3 ways to keep track of the parity:

  1. zip the sorting range with a trivial 0, 1... n sequence and read the permutation after sorting. (this is a sure way, but it does an unreasonable amount of extra work).
  2. hack the comparison operation to flip a sign each time a given pair is unsorted. Of course, this is bound to fail in general, as I don't know if the number of permutations is the same as the number of "failed" comparisons.
  3. wrap the sequence in a type with a custom swap that has the side-effect of keeping a count or the sign of the permutations so far.

Of course, these are all horrible solutions; I am looking for something better if it is available: Is there an algorithm close to std::sort that could allow me to keep track of the parity without having to reimplement sort from scratch?

alfC
  • 14,261
  • 4
  • 67
  • 118
  • I guess you must implement your own sorting algorithm. Just because the comparison operator returns false is no indication that `std::sort` is about to swap the two values. – j6t Mar 13 '23 at 10:37
  • Would [std::stable_sort](https://en.cppreference.com/w/cpp/algorithm/stable_sort) suit your needs? – Jesper Juhl Mar 13 '23 at 10:37
  • Option 1 does not seem like an unreasonable amount of work to me, especially if the alternative is writing your own sorting code. – john Mar 13 '23 at 10:39
  • Can you go into how parity is calculated? `std::sort` is permitted to move values into temporaries, so you might not be swapping the ith and jth values, you might be moving the ith element into a temporary, then later moving (potentially some other) temporary into the jth element. Option 1 seems like the only portable solution. – Caleth Mar 13 '23 at 10:41
  • @JesperJuhl, I have the same problem whether I have total order or not. (I am ordering lexicographic sequences). But your suggestion raises an interesting property of parity: only meaningful swaps should count, self-swap or swap of equal elements shouldn't count. (in general, if there are equal elements, algorithms stop or assign a "determinant" of zero and bail). – alfC Mar 13 '23 at 10:52
  • Why would you say that Option 1 leads to an unreasonable amount of extra work? You don't actually need to zip the ranges, but could just sort the sequence of indices: https://stackoverflow.com/a/12399290/12173376 – joergbrech Mar 13 '23 at 11:58
  • As long as you either sort the values in conjunction with the indices, or just sort the indices, then subsequently finding the parity of a permutation of 0,1,..,(n-1) is just an O(n) operation anyway - smaller than the order of the sorting in the first place. – lastchance Mar 13 '23 at 13:25
  • @lastchance, But I need both the parity and the ordering. I guess I can order iota and the from the ordered iota calculate the parity *and* actually sort the range. I guess doing this, *is* the way to go and even save by only doing the "possibly-large" object swaps in the last step. – alfC Mar 13 '23 at 16:14
  • @alfC - my answer (below) gives you both the parity and the ordering. The latter is via the permuted indices, but if you need the actual sorted array then just replace my cout statements by a copy into a pristine new vector. BTW, iota is just a function, not something you order. – lastchance Mar 13 '23 at 16:16
  • Yes, your answer gives both and during the calculation of the parity, it can do the actual swapping of the original range. Yes, I understand that iota is not the sequence. A problem with doing the swaps at the end is that the access to the original range will be completely random and will not use the cache. But I guess that is unavoidable and will also happen at the start of the direct sort. – alfC Mar 13 '23 at 16:23

1 Answers1

2

As suggested, you can just sort indices (with comparator function based on the original array at those indices). The parity can then be checked by an O(n) function following cycles in the permuted indices.

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

bool parity( const vector<int> &V )    // returns true for even, false for odd
{                                      // V is a permutation of 0, 1, ..., n-1 (NOTE: zero-based!)
   vector<bool> visited( V.size(), false );
   bool result = true;
   for ( int start = 0; start < V.size(); start++ )
   {
      if ( visited[start] ) continue;
      visited[start] = true;
      for ( int j = V[start]; j != start; j = V[j] )
      {
         result = !result;
         visited[j] = true;
      }
   }
   return result;
}


int main()
{
   vector<int> test = { { 17, 0, 19, 13, 4, -5, -6, 27, -31 } };

   vector<int> indices( test.size() );   iota( indices.begin(), indices.end(), 0 );
   sort( indices.begin(), indices.end(), [&test]( int i, int j ){ return test[i] < test[j]; } );
                   
   cout << "Sorted array: ";
   for ( int i : indices ) cout << test[i] << " ";
   cout << "\nParity: " << ( parity( indices ) ? "even" : "odd" ) << '\n';
}

Sorted array: -31 -6 -5 0 4 13 17 19 27 
Parity: odd
lastchance
  • 1,436
  • 1
  • 3
  • 12
  • I think there a better way to find cycles that doesn't need the allocation of the bool array. By keeping track of the lowest element in each cycle. I will try to find the reference. – alfC Mar 13 '23 at 16:25
  • vector is specially tailored to be very space-efficient: probably not much more than 1/32 the size of the original array (if an int is 32 bit). So I don't think going to great lengths to avoid this allocation is worth it. You could modify the original array (e.g. by adding n to each element during the search for cycles, then removing it at the end) - but this would mean extra addition/subtraction operations and necessitate removing the const in the argument (which can aid an optimising compiler). – lastchance Mar 13 '23 at 16:57