sorting dilemma

[henpecked1]

I'm doing a lab where I must use three sorting methods, then merge sort the three arrays. While separating the larger array, I'm getting a
"run time check error #2 stack around the variable x was corrupted:

It does this for y and z as well. I think it is happening where I break up the bigarray into smaller ones, but not sure, and cannot figure out why it's happening. The code is below:

int main()
{
	int bigarray[151];
	int x[50];
	int y[50];
	int z[50]; 

	srand ((unsigned) time(NULL)); 
	
	for (int i=0; i<151 ;i++) 
	{
		bigarray[i]=rand()%1000;
		cout<< " "<<bigarray[i];
	}


	cout <<endl<<endl<<endl;
	cout<<" 1 A...THIS IS THE FIRST UNSORTED 50 ELEMENTS OF THE ARRY "<<endl;
    
	for(int i=0; i < 50; i++)// this is
         {
           x[i] = bigarray[i];
           cout <<" "<<x[i];
         }

	cout<<endl<<endl<<endl<<endl<<"2 A...THIS IS THE SECOND 50 ELEMENTS OF THE ARRAY "<<endl<<endl;
          
	for(int i=50; i < 101; i++)
         {
           y[i] =bigarray[i];
           cout <<" "<<y[i];
         }

	cout<<endl<<endl<<endl<<endl<<" 3 A ... THIS IS THE THIRD 50 ELEMENTS OF THE ARRAY "<<endl;
         
	for(int i=100; i < 151; i++)
         {
           z[i] =bigarray[i] ;
           cout <<" "<<z[i];
		 }

	insertion_sort(x);
	selection_sort(y);
	bubble_sort(z);
	merge_sort(x, y, z);

 return 0;
}

the cpp definitions for the header:

void insertion_sort(int x[])
	{
	  int key,i;
	  for(int j=0;j<50;j++)
	  {
		 key=x[j];
		 i=j-1;
		 while(x[i]>key && i>=0)
		 {
				   x[i+1]=x[i];
			 i--;
		 }
		 x[i+1]=key;
	  }
	}


void selection_sort(int y[])
	{
	   int tmp;
	   int min;
	   for(int  i=0;i<50;i++)
	   {
	     min = i;
         for(int  x=i; x<50; x++)
		   {
			if(y[x] < y[min])
			 {
				min = x;
			 }
		   }
		  tmp = y[i];
		  y[i] = y[min];
		  y[min] = tmp;
		}
    }



void bubble_sort(int z[])
{
	int i,j;
	for(i=0;i<50;i++)
	{
		for(j=0;j<i;j++)
		{
			if(z[i]>z[j])
			{
				int temp=z[i];  
				z[i]=z[j];
				z[j]=temp;
			}

		}

	}

}


void merge_sort(int x[], int y[], int z[])
{
     int indexx = 0;     // initialize the Array Indices
     int indexy = 0;
     int indexz = 0;

     while((indexx < 50) && (indexy < 50))
     {
          if (x[indexx] < y[indexy])
          {
                 z[indexz] = x[indexx];
                 indexx++;    //increase the index
          }
         else
         {
                 z[indexz] = y[indexy];
                 indexy++;      //increase the index
         }
        indexz++;      //move to the next position in the new array
     }
     // Push remaining elements to end of new array when 1 feeder array is empty
     while (indexx < 50)
     {
           z[indexz] = x[indexx];
           indexx++;
           indexz++;
     }
     while (indexy< 50)
     {
           z[indexz] = y[indexy];
           indexy++;
           indexz++;
     }
     return;
}

The header:

#pragma once


void insertion_sort(int x[]);

void selection_sort(int y[]);

void bubble_sort(int z[]);

void merge_sort(int x[], int y[], int z[]);

[vmanes]

OK, this is a sneaky one.

First of all, you've made a big error when you're loading the y and z arrays - you start their loops at a value other than 0. Look at your code below:

for(int i=0; i < 50; i++)// this is
         {
           x[i] = bigarray[i];
           cout <<" "<<x[i];
         }

	          
	for(int i=50; i < 101; i++)
         {
           y[i] =bigarray[i];
           cout <<" "<<y[i];
         }

You've filled the x array, element indexes 0-49 - fine! Then you start y array at index 50, and go to <101, which if you count on your fingers you'll find is 51 elements - OOPS. Double OOPS, array y should have started at index 0. The way memory usually gets laid out (with no optimization going on, anyway), the x array is at higher memory address than y array, which is higher than z array. All your array writing has occurred in the x array (three times) and by going to indexes limited by <101 and <151, you've written to the element one past the end of x array. That's what fires the warning.

Solution to this - use a separate index for reading from bigarray, restart each of x, y, z at the same 0, like:

int i, j = 0;
	for( i=0; i < 50; i++, j++)// this is
         {
           x[i] = bigarray[j];
           cout <<" "<<x[i];
         }

         //j starts at 50 for this loop
	for(i=0; i < 50; i++,j++)
         {
           y[i] =bigarray[j];
           cout <<" "<<y[i];
         }
 //and again for the z array

[henpecked1]

I think I see what you mean with the incrementing i++ for x j++ for y and say k++ for z. I thought it might have something to do with the counts, but I couldn't see where I was off. I didn't think you had to restart from 0 every time, I thought you just started from a different index.

hmm, still giving me that error on y and z after changing the code to this:

int main()
{
	int bigarray[151];
	int x[50];
	int y[50];
	int z[50]; 

	srand ((unsigned) time(NULL)); 

	int i=0;
	int j=0;
	int k=0;

	for (int i=0; i<151 ;i++) 
	{
		bigarray[i]=rand()%1000;
		cout<< " "<<bigarray[i];
	}


	cout <<endl<<endl<<endl;
	cout<<" 1 A...THIS IS THE FIRST UNSORTED 50 ELEMENTS OF THE ARRY "<<endl;
    
	for(int i=0; i < 50; i++, j++, k++)// this is
         {
           x[i] = bigarray[i];
           cout <<" "<<x[i];
         }

	cout<<endl<<endl<<endl<<endl<<"2 A...THIS IS THE SECOND 50 ELEMENTS OF THE ARRAY "<<endl<<endl;
          
	for(int i=0; i < 50; i++, j++, k++)
         {
           y[i] =bigarray[j];
           cout <<" "<<y[i];
         }

	cout<<endl<<endl<<endl<<endl<<" 3 A ... THIS IS THE THIRD 50 ELEMENTS OF THE ARRAY "<<endl;
         
	for(int i=0; i < 50; i++, j++, k++)
         {
           z[i] =bigarray[k] ;
           cout <<" "<<z[i];
		 }

	insertion_sort(x);
	selection_sort(y);
	bubble_sort(z);
	merge_sort(x, y, z);

 return 0;
}

[henpecked1]

altered to match what you posted (for z as well, misunderstood)
Still gives me that error for y and z?

[vmanes]

I don't see any reason for warnings or errors around the y and z arrays. Please post the exact message, and line that it points to, if any.

Also, you don't need variable k, just set j to 0 at the beginning, let it be the index of bigarray in all three loops.

[henpecked1]

Okay, removed k completely, set j to be the index of big array in all three loops.

I no longer get the error for x, only for y and z. The error comes up in a windows dialog box and says

"run time check error #2 stack around the variable y was corrupted" and asks me if I want to abort, retry, or ignore. If I hit ignore, it says "run time check error #2 stack around the variable z was corrupted", and if I hit ignore for that, the program ends

[vmanes]

please post the current version of the code. I still don't see anything in what you posted above that should be problematic.

Whoa, look at your mergesort. You pass it the x, y, z arrays, each sized 50. Your function is merging the first two into the third - thus you're stuffing 100 items in the 50 element z array!!!!

Shouldn't the merge function be given all four of your arrays, merging x, y, z back into bigarray?

Do the error messages come up with y first, then z? I'd think it would be the other way.

[henpecked1]

yes, it comes up with y first, then z. It's definitely something I did in merge sort, when I comment it out I get no errors.

here's the merge sort that I messed up

void merge_sort(int x[], int y[], int z[])
{
     int indexx = 0;     // initialize the Array Indices
     int indexy = 0;
     int indexz = 0;

     while((indexx < 50) && (indexy < 50))
     {
          if (x[indexx] < y[indexy])
          {
                 z[indexz] = x[indexx];
                 indexx++;    //increase the index
          }
         else
         {
                 z[indexz] = y[indexy];
                 indexy++;      //increase the index
         }
        indexz++;      //move to the next position in the new array
     }
     // Push remaining elements to end of new array when 1 feeder array is empty
     while (indexx < 50)
     {
           z[indexz] = x[indexx];
           indexx++;
           indexz++;
     }
     while (indexy< 50)
     {
           z[indexz] = y[indexy];
           indexy++;
           indexz++;
     }
     return;
}

[vmanes]

in your main( ), change the function call for mergesort to:

merge_sort(x, y, bigarray);

Which is really what you want. Of course, this is not getting the z array data in, but you'll work on that later.

[henpecked1]

did that already, errors gone. Now how is array z brought into the mix?...other than adding it to the argument list.

Is it compared to x and y as well, or is it somehow compared to bigarray? I'm not sure how thats done

[henpecked1]

Here's the spot I'm having trouble with inside the merge sort, I'm not sure what happens inside the statement now

while((indexx < 50) && (indexy < 50) && (indexz < 50))
     {
          if (x[indexx] < y[indexy])
          {
                 bigarray[indexbigarray] = x[indexx];
                 indexx++;    //increase the index
          }
         else
         {
                 bigarray[indexbigarray] = y[indexy];
                 indexy++;      //increase the index
         }
        indexbigarray++;      //move to the next position in the new array
     }

[vmanes]

You could try writing the mergesort() to handle three input arrays, storing to a fourth bigarray, but that's an awkward way. We generally want to solve problems in terms of things that are already solved.

You know how to merge two arrays into one. There is no requirement that the two source arrays be of the same size, only that the destination be at least big enough to hold the total number of elements.

What if you have, in main, another array of at least size 100, which will be the temporary holding place for the result of merging x and y. Then, call mergesort( ) again, passing z and the temp array, with big array as the destination. This will require that mergesort() also be told the size of the source arrays. Side benefit is that now your mergesort will handle any size problem, not the just specific case of inputs of size 50. This more general approach means never having to revise the function when the problem scale changes. So, your prototype for mergesort ()might look like:

void mergesort ( int a[], int b[], int dest[], int size_a, int size_b );

use the size parameters as limits on index_a and index_b in the loops.

[henpecked1]

Okay, I got it, worked like a champ. Thanks for the advice, it worked fine.