runtime error returning memory

farmergeoff2003 (34)
I am getting runtime error running this prgm on my computer. When I step through it appears to occur when I return memory used by dynamic allocation at the end of main. When I run it on my schools system it works with no runtime error. Any ideas?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
int main()
{   
    // Declarations
    int iSize = 32, iCompares = 0;  // number of elements in first array
         
    double startTime, endTime; // store time values
    
    double dTime = 0,  // store time values
           dTime2 = 0,
           dTime3 = 0;
    
    do {
      
        long * laNumbers = new long[iSize],
             * laNumbers2 = new long[iSize],
             * laNumbers3 = new long[iSize];
         
        // fill arrays of rands for sorting
        for ( int x = 0; x < iSize; x++)
        {
            laNumbers[x] = rand();        // generate original array of rands
            laNumbers2[x] = laNumbers[x]; // make copies for each sort function
            laNumbers3[x] = laNumbers[x];
        }
    
        cout << "\n\nSorted " << iSize << " random numbers.";
    
    if ( dTime < MAX_TIME )
    {
        dTime = 0, iCompares = 0;
        startTime = clock();                 // get current clock value
        iCompares = bubbleSort(laNumbers, iSize);        // sort numbers
        endTime = clock();                   // get current clock value
        // calculate elapsed time
        dTime = (endTime - startTime)/static_cast<double>(CLOCKS_PER_SEC);
        printData(STRING, dTime, iCompares);      // print data from sort 
    }
    else 
        cout << "\n\n\t" << STRING << " is done.";

    if ( dTime2 < MAX_TIME )
    {
        dTime2 = 0, iCompares = 0;
        startTime = clock();                 // get current clock value
        iCompares = mergeSort(laNumbers2, 0, iSize);     // sort numbers
        endTime = clock();                   // get current clock value
        // calculate elapsed time
        dTime2 = (endTime - startTime)/static_cast<double>(CLOCKS_PER_SEC);
        printData(STRING2, dTime2, iCompares);     // print data from sort
    }
    else 
        cout << "\n\n\t" << STRING2 << " is done.";
        
    if ( dTime3 < MAX_TIME )
    {
        dTime3 = 0, iCompares = 0;
        startTime = clock();                  // get current clock value
        iCompares = shellSort(laNumbers3, iSize);         // sort numbers
        endTime = clock();                    // get current clock value
        // calculate elapsed time
        dTime3 = (endTime - startTime)/static_cast<double>(CLOCKS_PER_SEC);
        printData(STRING3, dTime3, iCompares);     // print data from sort
    }
    else 
        cout << "\n\n\t" << STRING3 << " is done.";
    
    delete [] laNumbers;   // return memory
    delete [] laNumbers2;  // return memory
    delete [] laNumbers3;  // return memory 
    
    iSize = iSize * 2;
   } while ( dTime2 < MAX_TIME );
kbw (9488)
What runtime error?
farmergeoff2003 (34)
I get a runtime on my PC but it runs fine off of the schools system. Just got a new computer and it does it on both but not the schools using UNIX. I am wondering if it has to do with my OS accessing the memory location. When I step through it'll give me the runtime at line 68. If I comment these out it workds fine: 
1
2
3
4
 
   
    delete [] laNumbers;   // return memory
    delete [] laNumbers2;  // return memory
    delete [] laNumbers3;  // return memory


but I know I need to free that memory.

kbw (9488)
Your sort routines are overwriting the memory blocks. Without seeing any of them, I can't comment further.
farmergeoff2003 (34)
I don't care if I overwrite the data after I complete the iteration of the entire WHILE loop that is MAIN. I'm trying to free the space anyway at the end of the WHILE and when the loop starts again I dynamically create 3 more arrays that are larger.

Each routine uses it's own array, I get no issues with incorrect data. Am I returning the memory space back correctly and dynamically creating it correct on each iteration? Here's the whole thing:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
 

#include <iostream>   //cin, cout functions
#include <cstdlib>    //exit function, rand()
#include <string>     //using strings
#include <time.h>     //for timer
using namespace std;
int main()
    int iSize = 32, iCompares = 0;  // number of elements in first array
         
    double startTime, endTime; // store time values
    
    double dTime = 0,  // store time values
           dTime2 = 0,
           dTime3 = 0;
    
    do {
      
        long * laNumbers = new long[iSize],
             * laNumbers2 = new long[iSize],
             * laNumbers3 = new long[iSize];
         
        // fill arrays of rands for sorting
        for ( int x = 0; x < iSize; x++)
        {
            laNumbers[x] = rand();        // generate original array of rands
            laNumbers2[x] = laNumbers[x]; // make copies for each sort function
            laNumbers3[x] = laNumbers[x];
        }
    
        cout << "\n\nSorted " << iSize << " random numbers.";
    
    if ( dTime < MAX_TIME )
    {
        dTime = 0, iCompares = 0;
        startTime = clock();                 // get current clock value
        iCompares = bubbleSort(laNumbers, iSize);        // sort numbers
        endTime = clock();                   // get current clock value
        // calculate elapsed time
        dTime = (endTime - startTime)/static_cast<double>(CLOCKS_PER_SEC);
        printData(STRING, dTime, iCompares);      // print data from sort 
    }
    else 
        cout << "\n\n\t" << STRING << " is done.";

    if ( dTime2 < MAX_TIME )
    {
        dTime2 = 0, iCompares = 0;
        startTime = clock();                 // get current clock value
        iCompares = mergeSort(laNumbers2, 0, iSize);     // sort numbers
        endTime = clock();                   // get current clock value
        // calculate elapsed time
        dTime2 = (endTime - startTime)/static_cast<double>(CLOCKS_PER_SEC);
        printData(STRING2, dTime2, iCompares);     // print data from sort
    }
    else 
        cout << "\n\n\t" << STRING2 << " is done.";
        
    if ( dTime3 < MAX_TIME )
    {
        dTime3 = 0, iCompares = 0;
        startTime = clock();                  // get current clock value
        iCompares = shellSort(laNumbers3, iSize);         // sort numbers
        endTime = clock();                    // get current clock value
        // calculate elapsed time
        dTime3 = (endTime - startTime)/static_cast<double>(CLOCKS_PER_SEC);
        printData(STRING3, dTime3, iCompares);     // print data from sort
    }
    else 
        cout << "\n\n\t" << STRING3 << " is done.";
    
    delete [] laNumbers;   // return memory
    delete [] laNumbers2;  // return memory
    delete [] laNumbers3;  // return memory 
    
    iSize = iSize * 2;
   } while ( dTime2 < MAX_TIME );
   
/*    cout << "\n\n";   // Testing
    for ( int x = 0; x < iSize; x++)
    {
        cout << laNumbers[x] << ", ";
    }  */

    cout << "\n\nPress ENTER to quit.";  // Halts program at end
    cin.get();
	return 0;
}

int bubbleSort(long array[], int iSize)
/*******************************************************************************
  Purpose:       Sorts a unsorted list of long integers        
  Precondition:  array has been properly stored in array
  Postcondition: the array is naturally returned in sequential order
  Accredidation: http://www.aihorizon.com/essays/basiccs/lists/sorting/bubble.htm
/******************************************************************************/
{
    int iCompare = 0;
    
    for ( int i = 0; i < iSize - 1; ++i )
    {
        for ( int j = 1; j < iSize - i; ++j )
        {
            if ( array[j-1] > array[j] )  
                swap( array[j-1], array[j] );  // swaps two values     
            iCompare++;
        }
    }  
    return iCompare;
}

void printData(string sSort, double dTime, int iCompares) 
/*******************************************************************************
  Purpose:       prints data after a function iteration        
  Precondition:  functions have completed iteration and time values are established
  Postcondition: the screen displays the relative data
/******************************************************************************/
{ 
    cout << "\n\n\tThe " << sSort << " took " 
         << dTime
         << " seconds for " << iCompares << " compares.";
    return;
}

int mergeSort(long array[], int begin, int end)
/*******************************************************************************
  Purpose:       sorts unsorted list of data       
  Precondition:  array has been properly load
  Postcondition: the array is naturally returned in sequential order
  Accredidation: Professor Larry Young powerpoint available on homepage
/******************************************************************************/
{
    int middle, iCompareOut = 0;

    if (begin < end)
    {
        middle = (begin + end) / 2;        // calculate middle position
        mergeSort(array, begin, middle);   // recursive call with 1st half of array
        mergeSort(array, middle + 1, end); // recursive call with 2nd half of array
        
        // merge the 2nd half into the 1st half of array
        iCompareOut = merge(array, begin, middle, end);  
    }
    return iCompareOut;
}

int merge(long array[], int low, int mid, int high)
/*******************************************************************************
  Purpose:       merge halfs of an array together to make one sorted sequence       
  Precondition:  array is filled correcly
  Postcondition: the array is naturally returned in sequential order
  Accredidation: post by xavier666 on 
                 http://www.daniweb.com/forums/thread263607.html
/******************************************************************************/
{
    int i = low,     // holds low start position in array
        j = mid + 1, // holds 2nd start position in array
        k = low,     // holds low position in 2nd dynamic array
        iCompareIn = 0;
        
    // dynamically create array to hold temp array 
    long * array_temp = new long[high + 1];

    while (i <= mid && j <= high) // doesn't let either position run into their max
    {
        if (array[i] < array[j])  // verify low is still < middle
            array_temp[k++] = array[i++]; // assign to temp array and increment
        else                              
            array_temp[k++] = array[j++]; // assign to temp array and increment
        iCompareIn++;
    }
    // finish filling the temp array after conditions cannot be met above
    while (i <= mid)     // if low is not yet to middle
        array_temp[k++] = array[i++];    // assign to temp array and increment

    while (j <= high)    // if mid is not yet to high                
        array_temp[k++] = array[j++];     // assign to temp array and 
    
    for (i = low; i < k; i++)  // copy the array back into original
        array[i] = array_temp[i];         
    
    delete [] array_temp;  // return memory no longer used
    
    return iCompareIn;
}

int shellSort(long laArray[], int iSize)
/*******************************************************************************
  Purpose:       merge halfs of an array together to make  one sequence        
  Precondition:  array is filled correcly
  Postcondition: the array is naturally returned in sequential order
  Accredidation: http://mathbits.com/mathbits/compsci/arrays/Shell.htm
/*******************************************************************************/
{
     long temp;
     
     int numLength = iSize,
         d = numLength,
         iCompares = 0;
         
     bool bFlag;
     
     while( bFlag || (d > 1))      // boolean flag (true when not equal to 0)
     {
         bFlag = false;           // reset flag to check for future swaps
         d = (d+1) / 2;
         
         for (int i = 0; i < (numLength - d); i++)
         {
             if (laArray[i + d] < laArray[i])
             {
                 temp = laArray[i + d];      // swap positions i+d and i
                 laArray[i + d] = laArray[i];
                 laArray[i] = temp;
                 bFlag = true;                  // tells swap has occurred
              }
              iCompares++;
         }
     }
     return iCompares;
}
kbw (9488)
1. bFlag is uninitialised in shellSort.
2. k is larger than high in merge, causing your buffer overrun.

And finally, on a point of style:
1
2
3
4
5
6
 
        for ( int x = 0; x < iSize; x++)
        {
            laNumbers[x] = rand();        // generate original array of rands
            laNumbers2[x] = laNumbers[x]; // make copies for each sort function
            laNumbers3[x] = laNumbers[x];
        }

used to be written in a more obvious style as:
1
2
3
4
 
        for ( int x = 0; x < iSize; x++)
        {
            laNumbers[x] = laNumbers2[x] = laNumbers3[x] = rand();
        }

That's why the assignment operator returns a reference to *this. It seems the C++ community has forgotten the old ways.
Last edited on
farmergeoff2003 (34)
In case anyone cares this was the problem:
[code
// merge the 2nd half into the 1st half of array
iCompareOut = merge(array, begin, middle, end);
][/code]
should be
[code
// merge the 2nd half into the 1st half of array
iCompareOut = merge(array, begin, middle, end + 1);
][/code]
kbw (9488)
end is already one beyond the end of the array.
Topic archived. No new replies allowed.