Insertion sort using vectors, not working

Mamba

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 
Dmytro Kovalov

This is the classic implementation of Insertion reverse algo.

template <class T>
void isort(vector <T> &ar){
    if(!ar.size()) 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;
        }
    }
}

Your issue here: Please do not swap the two values, with 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);

but move the value while it bigger than next one.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related