Vector Subscript Out of Range Error

[Griff0527]

Hello everyone. I am working on creating a stub that would allow me to swap out various sorting algorithms so that I can "plug in" the algorithms and run the various sorts. The below code is for Insertion Sort (yes, I know it is the slowest possible sort), but once I get it to work, I plan on doing Heap Sort, Merge Sort, Quick Sort, Radix Sort, and TimSort while collecting times from each one. The input file I am using has approximately 1/2 million values in order to give a better example of the variences in time.

I have included code for a timer to start just before the sorting algorithm and end just after the algorithm, then outputting the total amount of time the sort took. This information will be used to show quantifiable data for explaining the differences between the various choices of algorithms.

I've never seen the "Vector Subscript Out of Range Error" and can't determine the issue from researching C++ Forums or Daniweb. Can you point me in the right direction?

Thank you,

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

using namespace std;



int main()
{

    int i=0, j=0, key=0;
    std::vector<int> a;
    int start_s=clock(); //start timer
    ifstream readFile;
    readFile.open("inputData.txt");//open file
    if (readFile.is_open()) 
    {
        while (!readFile.eof())

        while (readFile >> a[i])
        {
        for (int i=1; i<a.size(); ++i) // use pre-increment to avoid unneccessary temporary object
        {
                key= a[i];
                j = i-1;
                while((j >= 0) && (a[j] > key))
                {
                        a[j+1] = a[j];
                        j -= 1;
                }
                a[j+1]=key;
        }
        }
    }
    readFile.close(); //close file
    int stop_s=clock();//stop timer
    cout <<"time: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl;//output timer

    return 0;
}

[Moschops]

while (readFile >> a[i])

Every time you try to write to the vector like this, you have to be sure that the element a[i] exists. Given that at the start, the vector is of size zero, this is not going to go well. You're trying to write to a part of the vector that does not exist.

Either make the vector big enough, or add to it using a function that automatically increases the size of the vector (such as push_back).

[tinstaafl]

You might something like this useful:

#include<iostream>
#include<iterator>
#include<fstream>
#include<vector>
#include<ctime>
using namespace std;
int main()
{
    int j=0, key=0;
    std::vector<int> a;
    int start_s=clock(); //start timer
    ifstream readFile;
    readFile.open("inputData.txt");//open file
    if (readFile.is_open())
    {
        while (!readFile.eof())
        {
            readFile >> key;
            if ( a.size() == 0)
            {
                a.push_back(key);
            }

            else if(a.size() == 1)
            {
                a.push_back(key);
                if(key < a[0])
                    a[1] = a[0];
                    a[0] = key;
            }

            else
            {
                for (int i=1; i<a.size(); ++i) // use pre-increment to avoid unneccessary temporary object
                {
                    j = i-1;
                    while((j >= 0) && (a[j] > key))
                    {
                        a[j+1] = a[j];
                        j -= 1;
                    }
                    a[j+1]=key;
                }
            }

        }

    }
    readFile.close(); //close file
    int stop_s=clock();//stop timer
    cout <<"time: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl;//output timer
    return 0;
}

[Griff0527]

Thank you both for the assistance. I have been able to correct it based on your responses. I'm amazed at how fast the InsertionSort completed with a half million numbers though, so now I'm going to add an output file to double check my work and insure that the sort is running correctly. It seems wrong to me that an insertion sort of half a million numbers should complete in just under 5 seconds.