Matthew Matthew - 9 days ago 5
C++ Question

insertion sort bizzare run time

I'm trying to sort a vector using insertion sort but for most values it fails to finish. if the vector size is greater than 3 the loop will not finish for an extended period of time, not at all, or it will finish quickly as expected up to values of 5 randomly.

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <vector>

void PRINT(std::vector<int> &data);


void insertion(std::vector<int> data, clock_t Time);

int main()
{
clock_t Time;
int dataSize, maxval;
std::vector<int> data;

srand(time(0));


std::cout<<"input vector size\n";
std::cin>>dataSize;
std::cout<<"input max value\n";
std::cin>>maxval;

Time=clock();
for(int i=0; i<dataSize; i++)
{
data.push_back(1+rand()%maxval);
}
Time=clock()-Time;
std::cout<<"ticks to randomize "<<Time<<" seconds "<<float(Time)/CLOCKS_PER_SEC<<std::endl;

insertion(data, Time);
return 0;
}

void PRINT(std::vector<int> &data)
{
std::cout<<"data contains: ";
for(int i=0; i<data.size(); i++)
std::cout<<data[i]<<", ";
std::cout<<std::endl;
}


void insertion(std::vector<int> data, clock_t Time)
{
bool sorted;
std::vector<int>::iterator j;

Time=clock();
for(int i=1; i<data.size(); i++)
{
j=(data.begin()+i-1);
sorted=false;

while(!(j==data.begin())&&!sorted)
{
if (*j<data[i])
{
sorted=true;
data.insert((j+1),data.at(i));
}

j--;
}

}
Time=clock()-Time;

std::cout<<"insertion:\nticks taken "<<Time<<"\n";
std::cout<<"seconds "<<float(Time)/CLOCKS_PER_SEC<<std::endl;
PRINT(data);
}


does anyone see why my implementation has such an insane run time at higher values? is there a better way to implement this?

Answer

Here is one glaring error.

std::vector<int>::iterator j;
//...
for (int i = 1; i < data.size(); i++)
{
    j = (data.begin() + i - 1);  // iterator j points to a location in the vector
    //...
    while (!(j == data.begin()) && !sorted)
    {
       //...
       data.insert((j + 1), data.at(i));   // vector being resized here
     }
     j--;  // this iterator is now invalidated!

The issue is that you are changing the size of the vector in the middle of the loop, and the j iterator that was pointing inside the vector becomes invalidated due to the vector being resized. You try and decrement the invalid iterator, and everything falls apart from there (running in Visual Studio shows a debug message box that the iterator is "not decrementable").

Either use straight indexing using an integer (not an iterator), or the technique shown at the link in my comment on implementing the insertion sort.