insertion sort bizzare run time

Question

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?

*is there a better way to implement this?* -- [Yes, there is](http://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c) — PaulMcKenzie, Nov 26 '16 at 22:07

score 0 · Accepted Answer · answered Nov 26 '16 at 22:18

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.

i tried indexing with an integer but vector.insert() requires an iterator. I will attempt the implementation in the link you posted though frankly I understood far too little of it. thanks for the help! — Matthew Mccall, Nov 26 '16 at 22:42
`vector.insert() requires an iterator.` -- This could have been solved by using `data.insert(data.begin() + i, ...)` assuming that `i` is the index. — PaulMcKenzie, Nov 28 '16 at 04:50

insertion sort bizzare run time

1 Answers1