DaniWeb Forum Index > Software Development > C++

sorting dilemma

Please support our C++ advertiser: Programming Forums - DaniWeb Sister Site

Thread Solved

•

Join Date: Dec 2007

Posts: 226

Reputation: henpecked1 is an unknown quantity at this point

Solved Threads: 1

henpecked1 henpecked1 is offline

Offline

Posting Whiz in Training

sorting dilemma

Sep 17th, 2008

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:

 Help with Code Tags 
 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:

 Help with Code Tags 
 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:

 Help with Code Tags 
 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[]);

•

Join Date: Aug 2007

Posts: 1,679

Reputation: vmanes is a splendid one to behold

Solved Threads: 193

vmanes

Offline

Posting Virtuoso

Re: sorting dilemma

Sep 18th, 2008

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:

 Help with Code Tags 
 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:

 Help with Code Tags 
 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

Everyone's gotta believe in something. I believe I'll have another drink.
~~~~~~~~~~~~~~~~~~
Looking for an exciting graduate degree? Robotics and Intelligent Autonomous Systems (RIAS) at SDSM&T See the program brochure here.

•

Join Date: Dec 2007

Posts: 226

Reputation: henpecked1 is an unknown quantity at this point

Solved Threads: 1

henpecked1 henpecked1 is offline

Offline

Posting Whiz in Training

Re: sorting dilemma

Sep 18th, 2008

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:

 Help with Code Tags 
 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.

•

Join Date: Dec 2007

Posts: 226

Reputation: henpecked1 is an unknown quantity at this point

Solved Threads: 1

henpecked1 henpecked1 is offline

Offline

Posting Whiz in Training

Re: sorting dilemma

Sep 18th, 2008

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.

•

Join Date: Aug 2007

Posts: 1,679

Reputation: vmanes is a splendid one to behold

Solved Threads: 193

vmanes

Offline

Posting Virtuoso

Re: sorting dilemma

Sep 18th, 2008

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.

•

Join Date: Dec 2007

Posts: 226

Reputation: henpecked1 is an unknown quantity at this point

Solved Threads: 1

henpecked1 henpecked1 is offline

Offline

Posting Whiz in Training

Re: sorting dilemma

Sep 18th, 2008

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

•

Join Date: Aug 2007

Posts: 1,679

Reputation: vmanes is a splendid one to behold

Solved Threads: 193

vmanes

Offline

Posting Virtuoso

Re: sorting dilemma

Sep 18th, 2008

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.

•

Join Date: Dec 2007

Posts: 226

Reputation: henpecked1 is an unknown quantity at this point

Solved Threads: 1

henpecked1 henpecked1 is offline

Offline

Posting Whiz in Training

Re: sorting dilemma

Sep 18th, 2008

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

 Help with Code Tags 
 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;
}

•

Join Date: Aug 2007

Posts: 1,679

Reputation: vmanes is a splendid one to behold

Solved Threads: 193

vmanes

Offline

Posting Virtuoso

Re: sorting dilemma

Sep 18th, 2008

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

Help with Code Tags

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.

•

Join Date: Dec 2007

Posts: 226

Reputation: henpecked1 is an unknown quantity at this point

Solved Threads: 1

henpecked1 henpecked1 is offline

Offline

Posting Whiz in Training

Re: sorting dilemma

#10

Sep 18th, 2008

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.