Insertion sort using vectors, not working

Question

Im trying to create an insertion sort algorithm using vectors, but instead of parsing the elements from the start of the array (vector here), i tried doing it from the end. The code does nothing but sort the element for the first time, and delete the first element of my vector. I want to know what correction to my code can I make for this to work. Basic procedure:

Start by element towards last (second last element)
Insert it in correct position in the 'sorted' subarray (vector) after it
Delete it from its initial position
Continue with algorithm, traversing backwards until vector's beginning

Code:

#include <iostream>
#include <vector>
using namespace std;

template <class T>
void isort(vector <T> &ar){
    //start from second last element upto first element
    for(auto i = ar.end()-2; i >= ar.begin(); i--){
        //iterator pointing towards element next to insertion element
        auto j = i + 1;
        //traverse and increase the pointer until condition met
        while(j != ar.end() && *i < *j) j++;
        //insert the insertion element at final position of the pointer
        ar.insert(j,*i);
        //erase the original element
        ar.erase(i);
    }
}
template <class T>
void display(vector <T> &ar){
    for(auto i = ar.begin(); i != ar.end(); i++){
        cout << *i << ' ';
    }
    cout << endl;
}
int main() {
    vector <int> X {6,1,7,1,3,2,6723,4,1,6};
    display <int>(X);
    isort <int>(X);
    display <int>(X);
}

Expected output:

6 1 7 1 3 2 6723 4 1 6 
1 1 1 2 3 4 6 6 7 6723

Output attained:

6 1 7 1 3 2 6723 4 1 6 
1 7 1 3 2 6723 4 1 6 1

*I want to know what correction to my code can I make for this to work* -- [What is a debugger ...](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — PaulMcKenzie, Feb 10 '22 at 16:17
Insertion into a vector can invalidate all existing iterators if it has to increase its capacity. — François Andrieux, Feb 10 '22 at 16:17
`i >= ar.begin()` is always `true` if `i` is a valid iterator for `ar`. If it isn't a valid iterator for `ar` then the comparison is not allowed. You cannot decrement an iterator to an element for which this condition becomes false. `ar.begin() - 1` is Undeifned Behavior. — François Andrieux, Feb 10 '22 at 16:19
[Look at the alternative to your code](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c). — PaulMcKenzie, Feb 10 '22 at 16:22
@FrançoisAndrieux but the loop runs finitely and terminates when `i` becomes less than `ar.begin()`. But for some reason with each itertion, no other part of the for loop is being executed, just `i` decreasing and finally the last `ar.erase(i)` is being executed, hence eliminating the first element — Mamba, Feb 10 '22 at 16:30
The most important thing @François Andrieux said, "_Insertion into a vector can invalidate all existing iterators_". And you are calling `ar.insert(...)`. And keeping your old iterators around without updating them. — lakeweb, Feb 10 '22 at 16:41
@Mamba Valid `i` can *never* become less than `ar.begin()`. An attempt to make it less than `ar.begin()` is undefined behaviour. — Evg, Feb 10 '22 at 17:07
@Mamba The loop only looks like it works when you tried it. Different build configurations or different architectures could change that. For example the compiler might in theory optimize the condition to just `true` because it is equivalent and faster. Or, you might change the container from `vector` to something else later. And then the comparison or decrement operation might crash or cause other undesired behavior. — François Andrieux, Feb 10 '22 at 18:18
@FrançoisAndrieux Ahh okay okaay, i have rectified that mistake in my code — Mamba, Feb 10 '22 at 19:35

Dmytro Kovalov · Accepted Answer · 2022-02-10T20:32:47.240

3

This is my implementation of Insertion reverse algo.

template <class T>
void isort(vector <T> &ar){
    if(ar.size() < 2)
        return;
    //start from second last element upto first element
    for(auto i = ar.end()-2; i >= ar.begin(); i--){

        auto j = i;
        //swap values until condition met
        while((j + 1) != ar.end() && *(j + 1) < *j) {
            //swap values
            auto tmp = *j;
            *j = *(j + 1);
            *(j + 1) = tmp;
            ++j;
        }
    }
}

The difference here it swaps the two values instead of insert/erase.

while(j != ar.end() && *i < *j) j++;
//insert the insertion element at final position of the pointer
ar.insert(j,*i);
//erase the original element
ar.erase(i);

edited Feb 10 '22 at 20:32

answered Feb 10 '22 at 17:11

Dmytro Kovalov

66
3

1

okay, thank you. i thought of making it using inert and erase just to try it out, but that apparently changes the iterators themselves, so swapping is a must – Mamba Feb 10 '22 at 17:33
4

Tactical note: Save some code and use `std::swap`. – user4581301 Feb 10 '22 at 17:42
1

`for(auto i = ar.end()-2; i >= ar.begin(); i--)` invokes undefined behaviour. You can't decrement `ar.begin()`. – Evg Feb 10 '22 at 20:28

Dmytro Kovalov · Answer 2 · 2022-02-10T21:11:17.683

1

About your way, so I modified a bit your code according to your solution, so it works now. The performance might be even worse than swapping, just because vector shifts elements after insert/erase.

#include <iostream>
#include <vector>
using namespace std;

template <class T>
void isort(vector <T>& ar) {
    if (ar.size() < 2)
        return;

    //start from second last element upto first element
    auto i = ar.end() - 2;
    do
    {
        //iterator pointing towards element next to insertion element
        auto j = i + 1;
        //traverse and increase the pointer until condition met
        while (j != ar.end() && *i > *j) ++j;
        //insert the insertion element at final position of the pointer

        if (*(j - 1) < *i && (j - 1) != i) {
            ar.insert(j, *i);
            i = ar.erase(i);
        }

        if (i == ar.begin())
            break;
        --i;
    } while (true);
}

template <class T>
void display(vector <T> &ar){
    for(auto i = ar.begin(); i != ar.end(); i++){
        cout << *i << ' ';
    }
    cout << endl;
}
int main() {
    vector <int> X {6,1,7,1,3,2,6723,4,6,1};
    X.reserve(X.size() * 2);
    display <int>(X);
    isort <int>(X);
    display <int>(X);
}

edited Feb 10 '22 at 21:11

answered Feb 10 '22 at 20:03

Dmytro Kovalov

66
3

3

`for(auto i = ar.end() - 2; i >= ar.begin(); --i)` invoked undefined behaviour. You can't decrement `ar.begin()`. – Evg Feb 10 '22 at 20:27
Added check on elements number. – Dmytro Kovalov Feb 10 '22 at 20:32
1

The number of elements is not *the* problem. The problem is that you decrement `i` when `i` is already equal to `ar.begin()`. That's why we have [reverse iterators](https://en.cppreference.com/w/cpp/iterator/reverse_iterator) as a separate concept. – Evg Feb 10 '22 at 20:33
It doesn't help. Take a look yourself: https://godbolt.org/z/xxv4Pzqsa – Evg Feb 10 '22 at 20:48
1

Decrementing `begin()` is undefined behaviour by the standard. If code appears to work in some implementation, it doesn't mean that that code is correct. "Appears to work" is one possible outcome of UB. – Evg Feb 10 '22 at 20:51
Plz take a look – Dmytro Kovalov Feb 10 '22 at 20:55

Insertion sort using vectors, not working

2 Answers2