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:

1. Start by element towards last (second last element)
2. Insert it in correct position in the 'sorted' subarray (vector) after it
3. Delete it from its initial position
4. 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 

CodePudding user response：

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

CodePudding user response：

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