Insert an element in a descending sorted array and keep array sorted-CodePudding

Assuming we have a sorted descending vector, like:

vector<int> array {26,  21,  13,  11,  8,  3,  2}.

I would like to insert a new and different element to the ones already present, so that descending sort of vector is kept.

Example flow:

I want to insert element 22, basically added at index 1, thus vector would be: 26, 22, 21, 13, 11, 8, 3, 2
I want to insert element 17, basically added at index 3, thus vector would be: 26, 22, 21, 17, 13, 11, 8, 3, 2
I want to insert element 1, basically added at a new index, thus vector would be: 26, 22, 21, 17, 13, 11, 8, 3, 2, 1
I want to insert element 43, basically added at index 0, thus vector would be: 43, 26, 22, 21, 17, 13, 11, 8, 3, 2, 1

A fast sample implementation in C would be:

#include<iostream> 
#include<vector> 
using namespace std; 
int get_Index_Insert(const vector<int>& array, int lengthArray, int insertValue) 
{ 
    int whereInsert = lengthArray; 
    for (int i = 0; i < lengthArray; i  ) 
    { 
        if (array[i] < insertValue) 
        { 
            whereInsert = i; 
            break; 
        } 
    } 
    return whereInsert; 
} 
vector<int> insert_Value(const vector<int>& arrayInput, int insertValue) 
{ 
    vector<int> arrayOutput; 
    int lenghtArray = arrayInput.size(); 
    // At what index to add? 
    int whereInsert = get_Index_Insert(arrayInput, lenghtArray, insertValue); 
    // Add it now: 
    for (int i = 0; i < whereInsert; i  ) 
        arrayOutput.push_back(arrayInput[i]); 
    arrayOutput.push_back(insertValue); 
    for (int i = whereInsert   1; i < lenghtArray   1; i  ) 
        arrayOutput.push_back(arrayInput[i - 1]); 
    return arrayOutput; 
} 
int main() 
{ 
    vector<int> array{26, 21, 13, 11, 8, 3, 2 }; 
    array = insert_Value(array, 22); 
    array = insert_Value(array, 17); 
    array = insert_Value(array, 1); 
    array = insert_Value(array, 43); 
    for (int i = 0; i < array.size(); i  ) 
        cout << array[i] << " "; 
    cout << endl << endl << endl; 
    return 0; 
}

Other info that may help in deciding recommended method:

I cannot use anything else than class vector from STL; (only using it as a holder it's push_back function, nothing else as helper function from it);
I will not have more than a 1000 elements ever in the vector.

Is there any way better to do it than above? in less complexity involved? Any source material I may have missed and that might help is very much appreciated also.

CodePudding user response：

Instead of creating a new vector you can use the insert function to put the new value into the existing list at the desired index. See https://en.cppreference.com/w/cpp/container/vector/insert

void insert_Value(const vector<int>& arrayInput, int insertValue) 
{ 
    int lenghtArray = arrayInput.size(); 
    // At what index to add? 
    int whereInsert = get_Index_Insert(arrayInput, lenghtArray, insertValue);
    arrayInput.insert(whereInsert, insertValue);
}

CodePudding user response：

#include <algorithm>
#include<iostream>
#include<vector>
using namespace std;
std::vector<int>::const_iterator get_Index_Insert(const vector<int>& array ,int insertValue) {
    return std::find_if(array.cbegin(),array.cend(),[insertValue](int aValue) { return aValue < insertValue;});
 }

void insert_Value(vector<int>& arrayInput, int insertValue, std::vector<int>::const_iterator aIt)
{
arrayInput.insert(aIt,insertValue);
}
int main()
{
    vector<int> array{26, 21, 13, 11, 8, 3, 2 };
    auto myIt = get_Index_Insert(array,22);
    insert_Value(array,22,myIt);
    for (int i = 0; i < array.size(); i  )
        cout << array[i] << " ";
    cout << endl << endl << endl;
    return 0;
}

This is only an idea, then it can be enhanced

CodePudding user response：

You don't need to pass the size of the vector, std::vector already have a member function size().

I think you overcomplicated things. You just have to iterate over the vector and compare each element with the value you want to insert. If the comparison evaluates to false, then you found where to insert the new element.

You may implement the function the following way:

template <typename val_t, typename Compare>
void insert_ordered(std::vector<val_t> & vec, const val_t & val, Compare comp)
{
    bool inserted(false);
    for(typename std::vector<val_t>::iterator it = vec.begin(); !inserted && (it != vec.end());   it)
    {
        if(!comp(*it, val))
        {
            vec.insert(it, val);
            inserted = true;
        }
    }
    if(!inserted)
        vec.push_back(val);
}

It takes the vector, the value to instert and the comparison function you want.

For your use case, it may be used like this:

int main()
{
    std::vector<int> v {26,  21,  13,  11,  8,  3,  2};

    insert_ordered(v, 22, std::greater<int>());
    insert_ordered(v, 17, std::greater<int>());
    insert_ordered(v, 1, std::greater<int>());
    insert_ordered(v, 43, std::greater<int>());

    for(const int & i : v)
        std::cout << i << ' ';

    return 0;
}

Output:

43 26 22 21 17 13 11 8 3 2 1

Live example

If, for some reason, you can't use std::greater, you can define your own comparator like this:

auto desc_comp = [](const int & lhs, const int & rhs)
{
    return lhs > rhs;
};

And use it like this:

insert_ordered(v, 22, desc_comp);

Edit:

If you don't mind having several exit points in the function, it can be simplified as:

template <typename val_t, typename Compare>
void insert_ordered(std::vector<val_t> & vec, const val_t & val, Compare comp)
{
    for(typename std::vector<val_t>::iterator it = vec.begin(); it != vec.end();   it)
    {
        if(!comp(*it, val))
        {
            vec.insert(it, val);
            return;
        }
    }
    vec.push_back(val);
}