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