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

Question

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>
#include <chrono>
using namespace std;
using namespace std::chrono;

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;
}

int get_Index_Insert2(const vector<int>& array, int lengthArray, int insertValue)
{
    int whereInsert = lengthArray;

    // Break out early if these cases:
    if (lengthArray == 0 || (array[lengthArray - 1] > insertValue))
        return whereInsert;
    
    // Otherwise do your binary magic:
    int low = 0;
    int high = lengthArray - 1;
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        if (array[mid] > insertValue)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    whereInsert = high + 1;
    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;
}

vector<int> insert_Value2(const vector<int>& arrayInput, int insertValue)
{
    vector<int> arrayOutput;
    int lenghtArray = arrayInput.size();

    // At what index to add? 
    int whereInsert = get_Index_Insert2(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()
{
    {
        // START TIME
        auto start = high_resolution_clock::now();
        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);
        auto stop = high_resolution_clock::now();
        // END TIME

        // Show time:
        auto duration = duration_cast<microseconds>(stop - start);
        cout << "Time taken by function 1, linear search: " << duration.count() << " microseconds" << endl;

        for (int i = 0; i < array.size(); i++)
            cout << array[i] << " ";

        cout << endl;
    }

    {
        // START TIME
        auto start = high_resolution_clock::now();
        vector<int> array{ 26,  21,  13,  11,  8,  3,  2 };
        array = insert_Value2(array, 22);
        array = insert_Value2(array, 17);
        array = insert_Value2(array, 1);
        array = insert_Value2(array, 43);   
        auto stop = high_resolution_clock::now();
        // END TIME

        // Show time:
        auto duration = duration_cast<microseconds>(stop - start);
        cout << "Time taken by function 2, binary search: " << duration.count() << " microseconds" << endl;

        for (int i = 0; i < array.size(); i++)
            cout << array[i] << " ";

        cout << endl;
    }

    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.

EDIT: After some more investigations and using binary search method while seeking index position for actual element insertion (thanks to the debates from comments), edited my above sample a bit, testing execution time of a "get_Index_Insert2(...) function using early returns and binary search.

Times received (microseconds), after 3 runs:

Time taken by function 1, linear search: 60 microseconds
43 26 22 21 17 13 11 8 3 2 1
Time taken by function 2, binary search: 33 microseconds
43 26 22 21 17 13 11 8 3 2 1

Time taken by function 1, linear search: 61 microseconds
43 26 22 21 17 13 11 8 3 2 1
Time taken by function 2, binary search: 34 microseconds
43 26 22 21 17 13 11 8 3 2 1

Time taken by function 1, linear search: 61 microseconds
43 26 22 21 17 13 11 8 3 2 1
Time taken by function 2, binary search: 34 microseconds
43 26 22 21 17 13 11 8 3 2 1

Answer 1

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);
}

Answer 2

#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

Answer 3

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);
}