Help with sorting even and odd numbers c++

[pigfire2]

I need help writing a loop to check an array of numbers and move the even numbers to the right side of the array.
I am stuck trying to write a loop to switch the numbers for it to display
something like 15, 3, 7, 2, 8

#include <iostream>
using namespace std;


int main() {
	int ary1[] = { 8, 15, 3, 7, 2 };
	int size1 = 5;

for (int i=0; i<size; i++) {
		 if ( ary[i]%2== 0 )
}
	return 0;
}

[keskiverto]

See std::partition

[pigfire2]

how do i write one without using library functions or another array
something like a bubble sort from what i've seen
I am trying to make it check with each number and switch it that way in a loop, but I am stuck on how to do it

[pigfire2]

I really need help with this I am limited to what I can use
so I think the best way would be to check each number with the next one, and switch it's place if it meets the odd on the left and even on the right. However, I forgotten how to do write a loop for this.

[keskiverto]

I said "see" (as in "read the documentation"), not "use". There is a piece of code there. However, it is a different challenge to filter out the irrelevant bits (that you probably have not encountered before) from it and recognize core idea within. The idea differs from sorting.

[D80DSL3A]

I solved this using while loops and two array indexes, left and right.
Start with left = 0 and right = size1-1.
Do ++left until the first even number is found.
Then --right until the last odd number is found.
Swap the numbers.
Keep going until left < right becomes false, then it's done!

I found I had to check that left < right is still true at each step. Don't want to walk one past the other.

Method bonus: If we do ++left before --right then left = index to 1st even number in array when the swapping is finished.

[pigfire2]

thanks for your suggestion, can i please have an example coding, I've never learned what you just typed before, but am familiar with arrays however it does sound correct

[JLBorges]

#include <iostream>

int main()
{
    int array[] = { 10, 13, 17, 11, 14, 15, 12, 19, 18, 16 };
    const int N = sizeof(array) / sizeof( array[0] ) ;
    for( int v : array ) std::cout << v << ' ' ;
    std::cout << '\n' ;

    // Start with left = 0 and right = size1-1
    int left = 0 ;
    int right = N-1 ;

    // Keep going until left < right becomes false, then it's done!
    while( left < right )
    {
        // Do ++left until the first even number is found.
        while( array[left]%2 == 1 && left < right ) ++left ;

        // Then --right until the last odd number is found.
        while( array[right]%2 == 0 && left < right ) --right ;

        // Swap the numbers.
        int temp = array[left] ;
        array[left] = array[right] ;
        array[right] = temp ;
    }

    for( int v : array ) std::cout << v << ' ' ;
    std::cout << '\n' ;
}

You wouldn't have learnt much from this till you actually write the code to partition an array on your own (that means: without looking at this while you write your code).

[D80DSL3A]

@JLBorges That's almost exactly the same as I wrote for this.
I chose to make a function for it:

// returns index to 1st even number in partitioned array
unsigned evensToRight( int a[], unsigned sz )
{
    unsigned left = 0, right = sz-1;
    while( left < right )
    {
        //find first even
        while( left<right && a[left]%2 != 0 ) ++left;
        // find last odd
        while( left<right && a[right]%2 == 0 ) --right;

        if( left<right )// swap the elements
        {
            int temp = a[left];
            a[left] = a[right];
            a[right] = temp;
        }
    }
    return left;
}

[Disch]

Your nested loops are unnecessary! This can be done in one pass!

O(n) (untested):

void evensToRight( int a[], int size )
{
    int left = 0;
    int right = size-1;

    while(left < right)
    {
        if( a[left]%2 )  // odd
        {
            ++left;
        }
        else  // even
        {
            int t = a[right];
            a[right] = a[left];
            a[left] = t;
            --right;
        }
    }
}

[pigfire2]

thanks disch that worked

how would you go about adding another array to the code

[JLBorges]

> Your nested loops are unnecessary! This can be done in one pass!

fun2code's algorithm is a one pass O(N) algorithm.

[PanGalactic]

I think it is great that y'all are doing people's homework assignments now. That's just swell.

[Disch]

Yeah I only did it because those guys already did.

[D80DSL3A]

@Disch. I tested your solution lightly but found it works fine, even when the array includes negative numbers (as does mine).

When testing on this array { 1, 4, 3, 5, 6, 2, 7, 9, 8 } and counting every while loop iteration, I get 11 for mine and 8 for yours (so yours a bit better there).
Clearly the number of ++left plus --right total to 8, then left == right.

The only downside I found with yours is that sometimes even numbers get swapped. With the above array yours swaps the 4 with the 8. Your total swaps = 3, but with mine = 2. This depends of course on where the even numbers fall in the starting array.
So, performance wise they seem pretty close.

BTW The homework isn't finished if op must figure out how to add other arrays.
But still...

[JLBorges]

> So, performance wise they seem pretty close.

Since the proffered 'improvement' is the very same algorithm as the original written slightly differently, the performance would be almost identical.

clang++
=======

random
-------------
  evensToRight_fun2code_original: 210 msecs.
  evensToRight_disch_improvement: 210 msecs.

only even
-------------
  evensToRight_fun2code_original: 70 msecs.
  evensToRight_disch_improvement: 100 msecs.

only odd
-------------
  evensToRight_fun2code_original: 60 msecs.
  evensToRight_disch_improvement: 70 msecs.

g++
===

random
-------------
  evensToRight_fun2code_original: 230 msecs.
  evensToRight_disch_improvement: 210 msecs.

only even
-------------
  evensToRight_fun2code_original: 80 msecs.
  evensToRight_disch_improvement: 80 msecs.

only odd
-------------
  evensToRight_fun2code_original: 60 msecs.
  evensToRight_disch_improvement: 70 msecs

.
http://coliru.stacked-crooked.com/a/5b61c48d27267f46

[keskiverto]

PanGalactic wrote:

I think it is great that y'all are doing people's homework assignments now.

I was wondering whether it was ok to mention the putative implementation of std::partition that is on this site's Reference section and concluded that the sample code there (btw, same algorithm as fun2code and JLBorges did post) still enforces thought. Besides, the later pigfire2's request for sample code shows that mentioning something failed to spoil the student.


@pigfire2
What do you mean by "add an array"?

[JLBorges]

> how would you go about adding another array to the code

Once it is written as a function, we can call it as many times as required.

#include <iostream>

// returns index to 1st even number in partitioned array
unsigned int evensToRight( int a[], unsigned int sz )
{
    unsigned left = 0, right = sz-1;
    while( left < right )
    {
        //find first even
        while( left<right && a[left]%2 != 0 ) ++left;
        // find last odd
        while( left<right && a[right]%2 == 0 ) --right;

        if( left<right )// swap the elements
        {
            int temp = a[left];
            a[left] = a[right];
            a[right] = temp;
        }
    }
    return left;
}

void print_partition( const int a[],  unsigned int n,  unsigned int pos )
{
    for( unsigned int i = 0 ; i < n ; ++i )
    {
        if( i == pos ) std::cout << " <-->  " ;
        std::cout << a[i] << ' ' ;
    }
    std::cout << '\n' ;
}

int main()
{
    int array[] = { 10, 13, 17, 11, 14, 15, 12, 19, 18, 16 };
    const unsigned int N = sizeof(array) / sizeof( array[0] ) ;
    const unsigned int pos = evensToRight( array, N ) ;
    print_partition( array, N, pos ) ;

    int array2[] = { 8, 6, 7, 4, 5, 2 };
    const unsigned int N2 = sizeof(array2) / sizeof( array2[0] ) ;
    const unsigned int pos2 = evensToRight( array2, N2 ) ;
    print_partition( array2, N2, pos2 ) ;
}

http://coliru.stacked-crooked.com/a/cdcc9b259ee147b6