Ad:

C++ Discussion Thread
Marked Solved
Views: 992

Page 1
2
Next

You are currently viewing page 1 of this multi-page discussion thread

Sep 17th, 2008

sorting dilemma

Expand Post »

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:

C++ Syntax (Toggle Plain Text)
 
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;
}
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:

C++ Syntax (Toggle Plain Text)
 
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;
}
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:

C++ Syntax (Toggle Plain Text)
#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[]);
#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[]);

Similar Threads

Sorting int array with stack class in C++

henpecked1

Reputation Points: 10

Solved Threads: 2

Posting Whiz in Training

Offline

244 posts
since Dec 2007

Permalink

Sep 18th, 2008

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:

C++ Syntax (Toggle Plain Text)
	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];
         }
	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:

C++ Syntax (Toggle Plain Text)
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
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

vmanes

Reputation Points: 1268

Solved Threads: 228

Posting Virtuoso

Offline

1,895 posts
since Aug 2007

Permalink

Sep 18th, 2008

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:

C++ Syntax (Toggle Plain Text)
 
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;
}
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;
}

Last edited by henpecked1; Sep 18th, 2008 at 12:27 am.

henpecked1

Reputation Points: 10

Solved Threads: 2

Posting Whiz in Training

Offline

244 posts
since Dec 2007

Permalink

Sep 18th, 2008

Re: sorting dilemma

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

Last edited by henpecked1; Sep 18th, 2008 at 12:35 am.

henpecked1

Reputation Points: 10

Solved Threads: 2

Posting Whiz in Training

Offline

244 posts
since Dec 2007

Permalink

Sep 18th, 2008

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.

vmanes

Reputation Points: 1268

Solved Threads: 228

Posting Virtuoso

Offline

1,895 posts
since Aug 2007

Permalink

Sep 18th, 2008

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

henpecked1

Reputation Points: 10

Solved Threads: 2

Posting Whiz in Training

Offline

244 posts
since Dec 2007

Permalink

Sep 18th, 2008

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.

vmanes

Reputation Points: 1268

Solved Threads: 228

Posting Virtuoso

Offline

1,895 posts
since Aug 2007

Permalink

Sep 18th, 2008

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

C++ Syntax (Toggle Plain Text)
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;
}
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;
}

henpecked1

Reputation Points: 10

Solved Threads: 2

Posting Whiz in Training

Offline

244 posts
since Dec 2007

Permalink

Sep 18th, 2008

Re: sorting dilemma

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

C++ Syntax (Toggle Plain Text)

	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.

vmanes

Reputation Points: 1268

Solved Threads: 228

Posting Virtuoso

Offline

1,895 posts
since Aug 2007

Permalink

Sep 18th, 2008

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

Last edited by henpecked1; Sep 18th, 2008 at 1:16 am.

henpecked1

Reputation Points: 10

Solved Threads: 2

Posting Whiz in Training

Offline

244 posts
since Dec 2007

Page 1
2
Next

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: please solve my problem

Next Thread in C++ Forum Timeline: Vector & reference Questions

DaniWeb Message

Cancel Changes

User Name
Password