C++ New Order for Structure Array

Question

I have a structure array, where each structure has an id (int) and an value called aktiv (boolean). I want to pass the structure array to a function which sorts the structure. The structures in the array with an aktiv value of 0 (false) should be at the end of my array.

I thought i create an second array where i save my values temporarly and then put everything from the second array again in the first, but it work. What am i doing wrong or what should i change. Thanks in advance. My code:

void naende(Item itf[], int dim) { 
Item* temp_arr = new Item[dim]{};
int temp = 0;
for (int i = 0; i < dim; i++) {
    if (itf[i].aktiv == 0) {
        temp_arr[dim - i].id = itf[i].id;
        temp_arr[dim - i].aktiv = itf[i].aktiv;
        //cout << temp_arr[i].id << endl;
    }
    else if (itf[i].aktiv == 1) {
        temp_arr[temp].id = itf[i].id;
        temp_arr[temp].aktiv = itf[i].aktiv;
        temp++;
    }
}

for (int j = 0; j < dim; j++) {
    itf[j] = temp_arr[j];
}
}

Answer 1

Given what you've posted, if the goal is to move all aktiv items that are 0 to the back of the array, then std::partition can be used.

#include <algorithm>

void naende(Item itf[], int dim) 
{ 
   std::partition(itf, itf + dim, [&](const Item& it) { return it.aktiv == 1; });
}

The code above places all aktiv entries equal to 1 to the left of the array, and all aktiv entries equal to 0 to the right of the array.

If the relative order needs to be maintained, then std::stable_partition can be used:

#include <algorithm>

void naende(Item itf[], int dim) 
{ 
   std::stable_partition(itf, itf + dim, [&](const Item& it) { return it.aktiv == 1; });
}

The point of the above code is to emphasize that there are STL algorithm or a set of STL algorithm functions that can be used to do a lot of work that would usually require a hand-coded solution (which would have to be debugged if there are errors). Using the functions above, the STL algorithm functions do not fail if given valid parameters.

---

Now let's say you can't use std::partition, and order need not be preserved. If this is the case, then the way this is accomplished can be to simply have two pointers, and call std::swap in a loop at strategic times.

The way it works is that you would have an index that goes forward in the array, and another index that starts at the end of the array and goes backwards. The incrementing of the first index, the decrementing of the end index, and the calls to std::swap would be done this way:

#include <algorithm>
#include <iostream>

struct Item
{
    int id;
    int aktiv;
};

void naende(Item itf[], int dim)
{
    int leftpos = 0;
    int rightpos = dim - 1;
    while (leftpos < rightpos)
    {
        if (itf[leftpos].aktiv == 0)
        {
            std::swap(itf[leftpos], itf[rightpos]);
            --rightpos;
        }
        else
            ++leftpos;
    }
}

int main()
{
    Item item[] = { {1,1},{2,0},{34,0},{32,1},{12,0},{12,1},{21,1} };
    naende(item, 7);
    for (int i = 0; i < 7; ++i)
        std::cout << item[i].id << " " << item[i].aktiv << "\n";
}

Output:

1 1
21 1
12 1
32 1
12 0
34 0
2 0

We basically only go forward with the left index if we detect that the aktiv value is 1. If it isn't 1, then we put that item in the back by swapping with the back item, then we decrement the back item index.

For stable items, I will leave that as an exercise.

Answer 2

your post is not clear, but you can try this :

#include <bits/stdc++.h>
using namespace std;

struct Item
{
    int active;
    int id;
};

void SortByStat(Item itf[], int dim)
{
    std::stable_partition(itf,itf + dim ,[](const Item &a){return a.active == 1;});

    //std::sort(itf, itf + dim, [](const Item &a, const Item &b) { return a.active < b.active; });
}

int main()
{
    Item arr[5] = {{0, 1}, {1, 2}, {0, 3}, {1, 4}, {1, 5}};
    int size = 5;
    for (int i = 0; i < size; i++)
    {
        cout << "id = " << arr[i].id << " => " << arr[i].active << endl;
    }

    cout << "After Sorting" << endl;

    SortByStat(arr, size);
    for (int i = 0; i < size; i++)
    {
        cout << "id = " << arr[i].id << " => " << arr[i].active << endl;
    }
}

Answer 3

Here's my implementation without std::partition.

#include <iostream>

struct Item {
    int id;
    bool aktiv;
};

//in-place swap
void swap(Item& left, Item& right) {
    left.aktiv ^= right.aktiv;
    right.aktiv ^= left.aktiv;
    left.aktiv ^= right.aktiv;
    left.id ^= right.id;
    right.id ^= left.id;
    left.id ^= right.id;
}

void naende(Item itf[], const size_t dim) {
    if (dim < 2) return;    //array is empty or has one single item, so do nothing
    Item temp = itf[0];     //init the temp to take the first item (adds only 1 more item in memory space)
    size_t rightSwapIndex = dim-1;  //index to put the checked item at the rightmost position
    size_t leftSwapIndex = 0;       //index to put the checked item at the leftmost position
    for (size_t i = 0; i < dim; ++i) {  //consider exactly 'dim' cases (guarantees algorithm to be O(n) time)
        if (!temp.aktiv) {  //needs to moved to the rightmost position
            swap(temp, itf[rightSwapIndex--]);  //swap the temp with the last item; and move the rightSwapIndex to left by one
        } else {
            itf[leftSwapIndex] = temp;      //put the temp at the rightmost index (may have no effect but important!)
            temp = itf[++leftSwapIndex];    //take the next item to consider; and move the leftSwapIndex to right
        }
    }
}

void printDebug(Item array[], const size_t dim) {
    for (size_t i = 0; i < dim; ++i) {
        std::cout<<array[i].id<<"/"<<array[i].aktiv<<" ";
    }
    std::cout<<std::endl;
}

int main() {
    //build some test array with a sample data
    size_t size = 10;
    Item array[size];
    for (size_t i = 0; i < size; ++i) {
        array[i].id = i;
        array[i].aktiv = i%2;   //TODO: test with some other inits as well, like for ex. this one: array[i].aktiv = (i%3)%2;
    }

    //test the function naende()
    printDebug(array, size);    //print out the array before the call
    naende(array, size);        //call our cute function
    printDebug(array, size);    //print out the array after the call
}

Output:

0/0 1/1 2/0 3/1 4/0 5/1 6/0 7/1 8/0 9/1 
9/1 1/1 7/1 3/1 5/1 6/0 4/0 8/0 2/0 0/0 

Another output with a different array init (see my comment line above with TODO:)

0/0 1/1 2/0 3/0 4/1 5/0 6/0 7/1 8/0 9/0 
7/1 1/1 4/1 3/0 5/0 6/0 2/0 8/0 9/0 0/0