Building a special order of elements for

std::sort + custom sorting function:

#include <iostream>
#include <numeric>
#include <iterator>
#include <algorithm>

struct CustomSort
{
    bool operator()(int lhs, int rhs)
    {
             if (lhs%2 != 0 && rhs%2 != 0)
            return lhs < rhs;
        else if (lhs%2 == 0 && rhs%2 == 0)
            return rhs < lhs;
        else
            return lhs%2 != 0;
    }
};

int main()
{
   const size_t N = 20;
   int a[N];

   std::iota( std::begin( a ), std::end( a ), 1 );

   for ( int x : a ) std::cout << x << ' ';
   std::cout << std::endl;
   std::sort( std::begin( a ), std::end( a ), CustomSort() );
   for ( int x : a ) std::cout << x << ' ';
   std::cout << std::endl;
}

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

EDIT: simplified sort a little

Last edited on

Well. Now consider the situation when it is not necessary that the original sequence has interchange of odd and even numbers. Consider that I showed indexes of elements not their values. For example

values:   3 6 4 8 1 7
indexes: 1 2 3 4 5 6

need to get

values:   3 4 1 7 8 6
indexes: 1 3 5 6 4 2

Then how to do the task?

in that case, can't you use MiiniPaa's algorithm using structs with value and index as members?

@abhishekm71

Well, then could you show how you are going to use indexes in a standard algorithm (or in the sort) instead of values of iterators?

Two algorithms:

#include <iostream>
#include <numeric>
#include <iterator>
#include <algorithm>

int main()
{
    const size_t N = 20;
    int a[N];

    std::iota( std::begin( a ), std::end( a ), 1 );

    for ( int x : a ) std::cout << x << ' ';
    std::cout << std::endl;

    std::reverse(std::stable_partition(std::begin(a), std::end(a),
                                       [a](int& x){return !((&x - a)%2);} ),
                 std::end(a));

    for ( int x : a ) std::cout << x << ' ';
    std::cout << std::endl;
}

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

If I have understood the problem correctly, if you enter

3 6 4 8 1 7

as input, you should get

3 4 1 7 8 6

as output. Please tell me if I have mis-understood the problem.

Wait. Does it need to modify existing array or we can copy elements into another container? In later case partition_copy will shine.

@abhishekm71

You have understood the problem correctly. If there is some array of integers shown as a sequence of its elements

a[0], a[1], a[2], a[3], a[4], a[5], a[6] /* 6 is an arbitrary size of the array */

then you need to rebuild the array the following way releative to the original sequence

a[0], a[2], a[4], a[6], a[5], a[3] a[1]

@MiiNiPaa

The original task is rebuild the array in place. But if you will show an alternative with creating another array based on the original array it will be not bad.

EDIT: oh, @MiiNiPaa I am sorry you need to build a new array based on the original.

Last edited on

I already shown in-place modification using two algorithms

Here is copy solution:

#include <iostream>
#include <numeric>
#include <iterator>
#include <algorithm>
#include <array>

int main()
{
    const size_t N = 20;

    int a[N];
    std::iota( std::begin( a ), std::end( a ), 1 );

    for ( int x : a ) std::cout << x << ' ';
    std::cout << std::endl;

    std::array<int, N> dest;
    std::partition_copy(std::begin(a), std::end(a), dest.rbegin(), dest.begin(),
                        [a](int& x)->bool{return (&x - a)%2;} );

    for ( int x : dest ) std::cout << x << ' ';
    std::cout << std::endl;
}

Last edited on

sorry vlad I see your point. I will have to use vectors and complicate the code a bit to implement struct. following is the code:

#include <iostream>
#include <numeric>
#include <iterator>
#include <algorithm>
#include <vector>

struct mydata {
  int index;
  int value;
};

struct CustomSort
{
    bool operator()(mydata lhs, mydata rhs)
    {
             if (lhs.index%2 != 0 && rhs.index%2 != 0)
            return (lhs.index < rhs.index);
        else if (lhs.index%2 == 0 && rhs.index%2 == 0)
            return (rhs.index < lhs.index);
        else
            return (lhs.index)%2 != 0;
    }
};

int main()
{
   const size_t N = 10;
   std::vector<mydata> a;
   for (size_t i=0; i<N; i++) {
     int val;
     mydata temp;
     std::cin >> val;
     temp.index = i+1;
     temp.value = val;
     a.push_back(temp);
   }
//   std::iota( std::begin( a ), std::end( a ), 1 );

   for ( mydata x : a ) std::cout << x.value << ' ';
   std::cout << std::endl;
   std::sort( a.begin(), a.end(), CustomSort() );
   for ( mydata x : a ) std::cout << x.value << ' ';
   std::cout << std::endl;
}

DeXecipher (458)

its a simple linear progression:

a:= initial term
d:= difference
x:= x entry

element(x) = dx+a
a = 1;
d = 2;

//all odd numbers
element(x) = 2x+1

even is not odd so you must adjust the formula:

1
2

//a = 0 for even numbers starting at x = 0
element(x) = 2x

EDIT:
And I don't think you guys should post an entire solution because this sounds like a homework problem for programming.

Last edited on

@DeXecipher
Read entire thread (or at least this message: http://www.cplusplus.com/forum/general/103542/#msg557814 )
Your "Algorithm" will not make sequence 10 45 63 23 86 52 43 99 into 10 63 86 43 99 53 23 45 as vlad from moscow needs.

TheIdeasMan (6794)

Gee, I thought Vlad was way past needing to do his homework 8+)

DeXecipher (458)

Ah my algorithm only works up to 19. In pseudo-code:

1
2

if x > 9
do element at x = (-2x)+20

Last edited on

@MiiNiPaa

You are right. But the realizations can be written simpler.

In place (requires two algorithms)

size_t i = 0;

std::reverse( std::stable_partition( std::begin( a ), std::end( a ), 
			             [&i]( int ) { return ( i++ % 2 == 0 ); } ),
	      std::end( a ) );

And when arrays are being copied

size_t i = 0;

std::partition_copy( std::begin( a ), std::end( a ), 
	             std::begin( b ), std::reverse_iterator<int *>( std::end( b ) ),
                     [&i]( int ) { return ( i++ % 2 == 0 ); } );

Last edited on

Well, I did both. I didn't find any notes that predicate will be applied in order (I had serious problems with that once), so I did index calculation in-place. Scott Meyers in "Effective STL" (AFAIR) also advises against functions with saved state in STL algorithms.

And it is interesting can anybody to suggest another standard algorithm for this task?:)

Last edited on

@MiiNipaa

Wow! it was a treat to read your solution(s). Only thing is that I think the lambda function should return the "not" of what it is returning right now. Am I right?