sorting dilemma
 

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[]);

Re: sorting dilemma
 

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

Re: sorting dilemma
 

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;

}

Re: sorting dilemma
 

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

Re: sorting dilemma
 

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.

Re: sorting dilemma
 

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

Re: sorting dilemma
 

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.

Re: sorting dilemma
 

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;

}

Re: sorting dilemma
 

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.

Re: sorting dilemma
 

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