Access Violation - insertionSorting arrays

[Smallboy]

I'm working on a homework assignment, for which I must do an insertion sort on an array of terms (term[]), while keeping each element of a corresponding array (freq[]) associated with the term.

The function breaks somewhere in the string library I think. I was thinking my code attempts to write to an array location that wasn't valid?


I receive the following error message

Unhandled exception at 0x59bbc0ed (msvcr100d.dll) in HW3.exe: 0xC0000005: Access violation reading location 0x00000001.

 void insertionSort(string term[], int freq[], int size){
	int i = 0, j = 0;
	string c = "       ";				/* temporary variable to store term*/
	int x = 0;					/* temporary variable to store freq*/

	for(i=1;i<size;i++){
		c = term[i];				/*store the examined element*/
		x = freq[i];
		j=i-1;	

		while ((c < term[j]) && (j >= 0)){	/*test if c is smaller than the element below it*/
			term[j+1] = term[j];
			freq[j+1] = freq[j];
			j--;
		}

		term[j+1] = c;
		freq[j+1] = x;
	}
}

Thanks for any help.

[Chervil]

Are you sure the error is in that function, rather than elsewhere in the program? i may have missed something, but i just put together a 'quick and dirty' program to test the above code and it seemed to work without problem.

[Smallboy]

Thanks for looking at it Chervil,

The entire length of code isn't very long, I'll post it here.


When I tested each other function, the code ran fine. Out of the three functions "read", "swap", and "insertionSort", "insertionSort" is the only one that results in this error.

#include <iostream>
#include <string>
#include <fstream>
using namespace std;

const int MAX = 5;

//swaps term[first] and freq[first] with term[second] and freq[second]
void swap(string term[], int freq[], int first, int second){

	string temp = " ";
	int tmp = 0;

	temp = term[first];
	tmp = freq[first];

	term[first] = term[second];
	freq[first] = freq[second];

	term[second] = temp;
	freq[second] = tmp;
	
}


void insertionSort(string term[], int freq[], int size){
	int i = 0, j = 0;
	string c = "       ";								/* temporary variable to store term*/
	int x = 0;									/* temporary variable to store freq*/

	for(i=1;i<size;i++){
		c = term[i];							/*store the examined element*/
		x = freq[i];
		j=i-1;	

		while ((c < term[j]) && (j >= 0)){		/*test if c is smaller than the element below it*/
			term[j+1] = term[j];
			freq[j+1] = freq[j];
			j--;
		}

		term[j+1] = c;
		freq[j+1] = x;
	}
}

void read(string term[]){
	
	string s = " ";
	int j = 0;

   ifstream fin("input.txt");    
    while (!fin.eof()) {
        fin >> s;			// s is a string variable to store a line of read text
		term[j] = s;
		j++;
    }
	fin.close();
}

int main(){

	string term[MAX];
	int freq[MAX];
	for(int i=0;i<MAX;i++){freq[i] = i+1;}
	
	read(term);


	for(int i=0;i<MAX;i++){cout << term[i] << " " << freq[i] << endl;}


	insertionSort(term,freq,MAX);


	cout << endl << endl;

	for(int i=0;i<MAX;i++){cout << term[i] << " " << freq[i] << endl;}



	system("pause");
	return 0;
}

[Chervil]

Most likely the error occurs in function read(). How many words do you have in the file "input.txt", is it more than MAX?

I'd suggest this, which checks that no more than MAX items are read. It also avoids looping on the condition eof() which is an error-prone approach and generally to be avoided:

void read(string term[])
{
    string s = " ";
    int j = 0;

    ifstream fin("input.txt");
    while (j < MAX && fin >> s )
    {
        term[j] = s;
        j++;
    }
    fin.close();
}

[Smallboy]

Thanks for that bit of code, that looks cleaner.

I'm still getting the same error however. I tried increasing the size of the const int MAX, as well as double checking my input.txt file. Neither of those has stopped the error.

For the sake of information, my txt file is this:


one
two
three
four
five


And the details present when the code stops are as follows:

*_First1 102 'f' const char
_Count 4 unsigned int
+ _First1 0x0105fa14 "four" const char *
- _First2 0x00000001 <Bad Ptr> const char *
CXX0030: Error: expression cannot be evaluated


I appreciate all the help so far, thanks for your time and knowledge.

[Chervil]

Thanks for the reply. It's getting a bit late where I live, so i have to leave this for now. Looks like you have Visual C++, I'm using a different compiler, but if there's an error it should still show up and so far I've not seen it.

Maybe someone else may have some ideas?

[Smallboy]

Thanks for your help, I'll keep searching!

[Chervil]

I think I found it. Possibly my compilers (two different ones) optimised the code and didn't hit the error.

Line 36 is tricky:

    while ((c < term[j]) && (j >= 0)){

The while loop has two conditions, c < term[j] and j >= 0
What happens when j reaches -1 ? The body of the loop should not be executed. But neither should the element term[-1] be accessed. As I understand things, if the first condition is false there is no need for the program to evaluate the second, as the whole condition must be false. I'd suggest re-writing it like this:

    while ((j >= 0) && (c < term[j])){

That should mean the program doesn't attempt to access the array with a negative subscript.

[Smallboy]

Hey that worked perfectly! That makes sense too, I always thought of that condition as one statement, so I thought it would never attempt to access term[-1]. Thanks for your help!