C++

Forum

 
Why is my sort changing my values?

Halo Fan (27)
My quicksort seems to change the values stored in my array. Here is my main program I have been using to test:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
int main()
{
	QuickSort test(10); //declares object 'test' of size 10
	cout << test.size(); //outputs size (10)

	cout << endl << endl;

	test.randomize(); //populates 'test' with random integers
	test.printSome(10); //Prints out my array

	test.sort(); //sorts the values in 'test'
	test.printSome(10); //Prints out my array

	cout << endl;

	return 0;
}


Here is the output I get from this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
10

757147
167851000
301413356
336971124
659598368
160567225
391749387
4890851
35766290
26239572

-33686019
757147
4890851
35766290
26239572
160567225
391749387
659598368
336971124
301413356


As you can see the values have changed somehow. Here are the relevant functions:

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
 
_int64 QuickSort::sort() 
{
	numops = 0; // will be used later to count significant operations...
	quicksort(theData, maxSize);
	return numops;
}

void QuickSort::quicksort(long theArray[], int n) 
{	
	int left = 0;
	int right = n;
	int temp;
	int pivot = (left+right)/2;

	while (left <= right) //Partition the array.
	{
		while (theArray[left] < theArray[pivot]) //Increment until we need to swap left.
			left++; 
		while (theArray[right] > theArray[pivot]) //Decrement until we need to swap right.
			right--;

		//Since we now need to swap...

		if (left <= right) //Avoids special case of done partitioning...
		{
			temp = theArray[left];
			theArray[left] = theArray[right];
			theArray[right] = temp;

			left++;
			right--;
		}
	} //End partitioning of the array.

	if (pivot > 1) //If left partition needs to be sorted...
		quicksort(theArray, pivot);
		
	if (pivot < n-2) //If right partition needs to be sorted...
		quicksort(theArray, (n-pivot-1) );
}


Thank you very much for any thoughts. Quicksort is giving me so much trouble and it's supposed to be so easy too!
Halo Fan (27)
In case it helps, here is my full header file and implementation of my SortData class and my QuickSort class (which is derived from SortData):

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
 
//my .h file
class SortData
{
public:
	SortData(int max = 100); 
		//uses the new operator to allocate theData array, with the size specified in the constructor parameter list.
		//sets maxSize (data from the protected section of the base class, of type int) to the specified size if a 
		//valid size (e.g. > 0) or to 100 by default.

	~SortData();
	
	int size() const; 
		//returns the size of theData array, which is an array of values of type long.
	
	void randomize(int seed = 1); 
		//fills the contents of theData array with data values obtained from the built-in random number generator. 
		//if no seed is specified when calling randomize(), the default of 1 is passed as the seed.
	
	void printSome(const int num = 10) const; 
		//prints out the first “num” values of theData, and the last “num” values of theData. If not specified, it will 
		//print out 10 data values by default (the first and last 5, if implemented that way).
	
	virtual _int64 sort() = 0;
		//integer datatype with 64 bits of magnitude. The standard int datatype has 32 bits of magnitude, and can 
		//represent values up to around 2 billion. The sort() method is defined as a pure virtual method, which 
		//must be implemented in any class derived from SortData. sort() sorts theData array, and returns a count (numops)
		//of the number of significant operations that were required. The count is kept track of within each derived 
		//class in a private piece of data called numops, of type _int64.

protected:
	long *theData;
	int maxSize;
};

class QuickSort : public SortData
{
public:
	QuickSort (int max = 100);
		//uses the new operator to allocate theData array, with the size specified in the constructor parameter list. 
		//the default size of theData array will be 100 if not specified. theData is a pointer to an array of type
		//long and is inherited from the protected section of the base class. 
		//sets maxSize (data from the protected section of the base class, of type int) to the specified size if a 
		//valid size (e.g. > 0) or to 100 by default.
	~QuickSort ();
	_int64 sort();
		//sorts theData array, and returns a count (numops) of the number of significant operations that were required. 
		//The count is kept track of within the private piece of data called numops, of type _int64.
private:
	_int64 numops;
	void quicksort(long theArray[], int n);
		//'helper' method to accomplish the actual sorting when called by the sort() function.
		//quicksort takes an array of data of type long and the size of that array as parameters and then sorts
		//the array. Once it is sorted, the public method will take over again and return numops.
};


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
 
//my .cpp file
#include "SortData.h"
#include <cstdlib>
#include <iostream>
using namespace std;


//--------------------------------------------------------------------------------------------------------------------
//Definition of SortData----------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------------------------

	//uses the new operator to allocate theData array, with the size specified in the constructor parameter list.
	//sets maxSize (data from the protected section of the base class, of type int) to the specified size if a 
	//valid size (e.g. > 0) or to 100 by default.
SortData::SortData(int max) 
{
	if (max > 1) //If the input is valid or not specified and defaults to 100...
	{
		theData = new long[max];
		maxSize = max;
	}
	else //If the input is invalid...
	{
		theData = new long[100];
		maxSize = 100;
	}
}

	//destructor
SortData::~SortData() 
{
	delete [] theData;
}

	//returns the size of theData array, which is an array of values of type long.
int SortData::size() const 
{
	return maxSize;
}


	//fills the contents of theData array with data values obtained from the built-in random number generator. 
	//if no seed is specified when calling randomize(), the default of 1 is passed as the seed.
void SortData::randomize(int seed)
{
	srand(seed);
	for(int i=0; i<maxSize; ++i)
		theData[i] = rand() * rand();
}


	//prints out the first “num” values of theData, and the last “num” values of theData. If not specified, it will 
	//print out 10 data values by default (the first and last 5, if implemented that way).
/*void SortData::printSome(const int num) const 
{
	for (int i = 0; i < num/2; i++)
		cout << theData[i] << endl;
	cout << endl;
	for (int j = maxSize-(num/2); j < maxSize; j++)
		cout << theData[j] << endl;
}*/
void SortData::printSome(const int num) const 
{
	for (int i = 0; i < num; i++)
		cout << theData[i] << endl;
	cout << endl;
}

//--------------------------------------------------------------------------------------------------------------------
//Definition of QuickSort---------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------------------------

	//uses the new operator to allocate theData array, with the size specified in the constructor parameter list. 
	//the default size of theData array will be 100 if not specified. theData is a pointer to an array of type
	//long and is inherited from the protected section of the base class. 
	//sets maxSize (data from the protected section of the base class, of type int) to the specified size if a 
	//valid size (e.g. > 0) or to 100 by default.
QuickSort::QuickSort (int max) 
{
	if (max > 1) //If the input is valid or not specified and defaults to 100...
	{
		theData = new long[max];
		maxSize = max;
	}
	else //If the input is invalid...
	{
		theData = new long[100];
		maxSize = 100;
	}
}


	//destructor
QuickSort::~QuickSort () 
{
	delete [] theData;
}


	//sorts theData array, and returns a count (numops) of the number of significant operations that were required. 
	//The count is kept track of within the private piece of data called numops, of type _int64.
_int64 QuickSort::sort() 
{
	numops = 0;
	quicksort(theData, maxSize);
	return numops;
}

	//'helper' method to accomplish the actual sorting when called by the sort() function.
	//quicksort takes an array of data of type long and the size of that array as parameters and then sorts
	//the array. Once it is sorted, the public method will take over again and return numops.
void QuickSort::quicksort(long theArray[], int n) 
{	
	int left = 0;
	int right = n;
	int temp;
	int pivot = (left+right)/2;

	while (left <= right) //Partition the array.
	{
		while (theArray[left] < theArray[pivot]) //Increment until we need to swap left.
			left++; 
		while (theArray[right] > theArray[pivot]) //Decrement until we need to swap right.
			right--;

		//Since we now need to swap...

		if (left <= right) //Avoids special case of done partitioning...
		{
			temp = theArray[left];
			theArray[left] = theArray[right];
			theArray[right] = temp;

			left++;
			right--;
		}
	} //End partitioning of the array.

	if (pivot > 1) //If left partition needs to be sorted...
		quicksort(theArray, pivot);
		
	if (pivot < n-2) //If right partition needs to be sorted...
		quicksort(theArray, (n-pivot-1) );
}
Last edited on
cire (8284)
Valid indices for arrays are 0 to size-1.

You set the index right to n on line 11 which would be an invalid index when quicksort is called from sort.

Halo Fan (27)
Thank you so much! A fresh pair of eyes really helps in finding such ridiculous things. Again, thank you!
Topic archived. No new replies allowed.