Attempting to sort arrays using for loops, however if/else if statements are not acting as I expected.

[JJDukes]

My goal is to create a function which will sort an array so that a specific number (int e), is moved to the back of the array, but the order of all the integers that are not equal to e is kept the same.

So, if int e = 2, and a[] = {3, 2, 5, 2, 6, 1, 8}

It would be sorted into: a[] = {3, 5, 6, 1, 8, 2, 2}

Below is what I created to try to solve this problem. The first for loop was just so I could easily compare int a[] sorted and unsorted.

#include "stdlib.h"
#include <iostream>
#include <cstdlib>
using namespace std;



int main()
{
    int a[] = {2, 1, 1, 2};
    int e = 2;
    int x = 3;
    int counter = 0;
    
    for (int i = 0; i <= x; i++){
     cout << i << "=" << a[i] << endl;   
    }
    cout << endl << endl;
    for (int i = 0; i <= x; i++){
        
        
        if (a[i] != e && a[x - counter] != e){
          
            cout << i << "=" << a[i] << endl;
            cout << "1 activated" << endl;
        }
        else if (a[i] == e && a[x - counter] != e) {
   
            a[i] = a[x - counter];
            a[x - counter] = e;
            counter = counter + 1;
            cout << i << "=" << a[i] << endl;
            cout << "2 activated" << endl;
        }
        else if (a[i] == e && a[x - counter] == e) {
             for ( ; a[x - counter] == e; counter++){
             }
             a[i] = a[x - counter];
             a[x - counter] = e;
             cout << counter << endl;
             cout << i << "=" << a[i] << endl;
             cout << "3 activated" << endl;
        }
    }
 
 return 0;   
}

This is the output:

0=2
1=1
2=1
3=2


1
0=1
3 activated
2
2=1
3 activated
3
3=1
3 activated

I can't figure out for the life of me why "if (a[i] != e && a[x - counter] != e)" and "else if (a[i] == e && a[x - counter] == e)" are not activating. So, for example, what I expected to happen after the first loop was that the first if statement would be triggered, since a[1] != e, and a[3 - 1] != e. Instead, nothing is triggered at all. Why is this happening?

[Handy Andy]

Hello JJDukes,

I am still working on understanding your code, but for now I was wondering in the second "if/else if" if the empty for loop is what you wanted?

else if (a[i] == e && a[x - counter] == e) 
{
	for (; a[x - counter] == e; counter++)
	{
	}
	a[i] = a[x - counter];
	a[x - counter] = e;
	std::cout << counter << std::endl;
	std::cout << i << "=" << a[i] << std::endl;
	std::cout << "3 activated" << std::endl;
}

Andy

[JJDukes]

Hey Andy, thanks for the reply. I'm pretty sure I have the for loop working the way I want it to. I just want to increase the value of the counter by 1 until it's found an appropriate place to swap variables. "Counter" just a number that denotes how many variables I'll have to move back from the last value in int a[] from. Int x is the amount of values in my array, and int e is the number I'm excluding. So, for example, if I've got:

int a[] = {2, 0, 0, 2, 2};

I'd like to swap the two to the very back of the array, but that'd be pointless since a[4] just happens to be the number I'm trying to exclude. The way I chose to deal with this is by creating that for loop. The counter is increased by one until it's gone back enough from a[x] to find a spot where it swap variables an actually do something. In this case, it'd be

a[4 - 0] == 2 loop triggers, adding 1 to counter
a[4 - 1] == 2 loop triggers, adding 1 to counter
a[4 - 2] == 0 loop's condition is false, a[4-2] and a[0] are swapped

At least, I think so. I can't really tell if the counter is working as intended, because for some reason only that else if statement is being triggered.

[dutch]

Here's one way of doing it.

#include <iostream>

int main() {
    int a[] = {3, 2, 2, 1, 2, 3, 4, 3, 2, 1, 2, 2, 2};
    int len = sizeof a / sizeof a[0];
    int e = 2;

    for (int i = 0; i < len; i++)
        std::cout << a[i] << ' ';
    std::cout << '\n';

    for (int to = 0, from = 0; from < len; ) {
        while (to < len && a[to] != e)
            ++to;
        from = to;
        while (from < len && a[from] == e)
            ++from;
        if (from < len) {
            a[to++] = a[from];
            a[from] = e;
        }
    }

    for (int i = 0; i < len; i++)
        std::cout << a[i] << ' ';
    std::cout << '\n';
}

[mbozzi]

This function exists already in the standard library. It is named std::stable_partition.

[Duthomhas]

The Standard Library’s stable_partition is pretty slick, but as a generalized function it cannot make some assumptions that could be significant.

For example, here are two other versions of a stable partition.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <vector>

#define EQUIVALENCE_EQ_IDENTITY 0
//#define EQUIVALENCE_EQ_IDENTITY 1 

Version 1: equivalence implies identity

#if EQUIVALENCE_EQ_IDENTITY
// This is a partition where it is recognized that
// equivalent items are IDENTICAL, meaning that any
// single x can be used to replace another.
// This is an O(n) complexity, O(1) space.
void partition( int x, int* xs, int n )
{
  int* froms = xs;
  int* tos   = xs;
  int* end   = xs + n;
  while (froms < end)
  {
    if (*froms != x) *tos++ = *froms;
    ++froms;
  }
  while (tos < end)
    *tos++ = x;
}
#endif 

Version 2: equivalence does not imply identity

#if !EQUIVALENCE_NE_IDENTITY
// This is a partition where equivalence is not 
// necessarily the same as identity, meaning that
// we cannot take the shortcut we took earlier.
// We can, however, still be pretty slick about it.
// It is an O(n) complexity, O(n) space.
void partition( int y, int* xs, int n )
{
  std::vector <int> ys;
  int* froms = xs;
  int* tos   = xs;
  int* end   = xs + n;
  while (froms < end)
  {
    if (*froms == y) ys.push_back( y );
    else             *tos++ = *froms;
    ++froms;
  }
  froms = ys.data();
  while (tos < end)
    *tos++ = *froms++;
}
#endif 

// A couple helper routines to get input
std::vector <int> ask_xs()
{
  std::vector <int> xs;
  std::cout << "xs? ";
  std::string s;
  getline( std::cin, s );
  std::istringstream ss( s );
  std::copy( 
    std::istream_iterator <int> ( ss ),
    std::istream_iterator <int> (),
    std::back_inserter( xs )
  );
  return xs;
}

int ask_x()
{
  std::cout << "x? ";
  std::string s;
  getline( std::cin, s );
  return std::stoi( s );
}

// Finally! Interesting stuff...
int main()
try
{
  for (auto xs = ask_xs(); !xs.empty(); xs = ask_xs())
  {
    auto x = ask_x();

    partition( x, xs.data(), xs.size() );

    for (auto x : xs)
      std::cout << x << " ";
    std::cout << "\n\n";
  }
}
catch (...) { }

Remember, when we are comparing items we have an equivalence function, like ==, that tells us whether we can consider the elements to be equivalent.

But comparing as equivalent does not necessarily imply that they are identical, which is to say, we cannot assume that replacing one element with an equivalent one will result in the same thing.

As the most basic example, family members can be considered equivalent in certain circumstances. “Hey, we’re having a party. Someone needs to invite the Schmidts.” In this case, it really doesn’t matter which family member you tell about the party.

However, being equivalent is not the same as identical. “Hey, can your brother drive us to the store?” “No. He doesn’t have a driver’s permit yet.” Clearly, when the police officer pulls you over he won’t pretend you are your brother. He’ll give you a ticket.

The same goes for data. Integers can be treated identically, but many classes of objects cannot. (The reasons run deep, much deeper down the rabbit hole than you may think. Explore some memory management pools to get there.)


Also, remember that a std::vector is a variable-length array replacement.

Were I using an array, I would have written:

  int xs[ SOME_BIG_NUMBER ];
  int xs_size = 0;

The problem with arrays is, of course, that I suddenly have to keep track of all kinds of stuff I really don’t want to —and vectors will do it for me for free! Yaay!

Hope this helps.

[JJDukes]

Update!

#include "stdlib.h"
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void displayArray (int a[], int x){
     for (int i = 0; i < x; i++){
         cout << i << " = " << a[i] << endl;
}
}

void compactArray (int a[], int x, int e){
    int backcounter = 0;
    int counter = 0;
    for (int i = 0; i < x; i++){
        
    if (a[i] != e){
        backcounter = backcounter + 1;
        if (counter > 0){
            a[i - i + backcounter - 1] = a[i];
            a[i] = e;
         
            }
        }
        else if (a[i] == e){
            counter = counter + 1;
        }
    }
}

int main()
{
    int x = 50;
    int a[x] = {};
    int e = 2;
    srand(static_cast<int>(time(0)));
      for (int i = 0; i < x; i++){
    a[i] = rand()%(5 - 1 + 1);
    }
    cout << endl << endl;
    displayArray (a, x);
    compactArray (a, x ,e);
    displayArray (a, x);

    return 0;
}

I've got it working with this code here. I'm extremely appreciative of everyone's information. I've only been taking programming classes for a semester, so I couldn't just start using new keywords, but it's pretty incredible to see from everyone how many ways there were to solve this problem. Thanks!