Sorting

antoin (7)
Can someone please help with this, it even confused my tutor. Although he is not great.
My header File
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
#include <iostream>
using namespace std;

class threeSorts
{
private:
	int arraySize;				//maximum size of the array
	int noOfItemsInArray;       //number of data items currently in the array
	int *anArray;
	int* arrayPointer;
	int partition(int* arrayPointer, int value1Index, int value2Index);
	void swap(int* arrayPointer, int value1Index, int value2Index);  //private member function that swaps two items in the array
	

public:
	threeSorts(int size);		// constructor
	void insert( int aValue);   // add item to array
	void display();
	void bSort();                    // Bubble/Exchange sort array
	void iSort();                    // Insertion sort array
	void sSort();                    // Selection sort array
	void qSort();
	
};


My Source file:
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
 
#include "threeSorts.h"

threeSorts::threeSorts(int size)
{   // constructor
	arraySize = size;
	noOfItemsInArray = 0;
	anArray = new int[size];      // create the array
}

		//function to swap two items in the array
void threeSorts::swap(int* arrayPointer, int value1Index, int value2Index)
{
	int temp;
	temp = arrayPointer[value1Index];
	arrayPointer[value1Index] = arrayPointer[value2Index];
	arrayPointer[value1Index] = temp;
}
		//function that adds an item to the array
void threeSorts::insert( int aValue)
{
	anArray[noOfItemsInArray] = aValue;
	noOfItemsInArray++;
}


		//function to display the items in the array
void threeSorts::display()
{
	for(int loop = 0; loop < noOfItemsInArray; loop++)
	{
		cout << anArray[loop] << " ";
	}
	cout << endl;
}



//This bubble/exchange sort function uses a slightly changed
//version of the algorithm on page 36 of the module handout.
//See the comments below to explain the change.
//Read the tutorial handout for a fuller explanation.
//
//You can improve this by making the adaptations suggested
//in the handout. I have not.
void threeSorts::bSort()
{
	int temp = 0;
	for( int i = 1; i<noOfItemsInArray; i++)
	{
		//The next line is slightly different from the algorithm
		//in the handout. We start j at the first element in the array - 0 -
		//and end j 2 short of the number of elements, otherwise in the
		//last loop anArray[j+1] would be undefined.
		for( int j = 0; j<(noOfItemsInArray-1); j++)
		{
			if(anArray[j] > anArray[j+1])
			{		//if (j-1)th > jth
				temp = anArray[j];			//swap the values
				anArray[j] = anArray[j+1];
				anArray[j+1] = temp;
			}
		}
	}
}


//This insertion sort function uses
//the algorithm on page 39 of the module handout.
//Read the tutorial handout for a fuller explanation.
void threeSorts::iSort()
{
	int inner, outer;
	int temp = 0;
	for( outer = 1; outer<noOfItemsInArray; outer++)
	{
		temp = anArray[outer];
		inner = outer;
		while(inner > 0 && anArray[inner-1]>=temp)
		{
			anArray[inner] = anArray[inner-1];
			--inner;
		}
		anArray[inner] = temp;
	}
}


//This Selection sort function uses
//the algorithm on page 38 of the module handout.
//Read the tutorial handout for a fuller explanation.
void threeSorts::sSort()
{
	int inner, outer;
	int position, value;

	for( outer = 0; outer<noOfItemsInArray - 1; outer++)
	{
		position = outer;
		value = anArray[position];
		for(inner = outer+1; inner < noOfItemsInArray; inner++)
		{
			if(anArray[inner] < value)
			{
				position = inner;
				value = anArray[position];
			}
		}
		value = anArray[outer];
		anArray[outer] = anArray[position];
		anArray[position] = value;
	}
}

int partition(int* arrayPointer, int value1Index, int value2Index)
{
	int pivot;
	int smallIndex;
	pivot = arrayPointer[value1Index];
	smallIndex = value1Index;

	for(int index = value1Index+1; index<=value2Index; index++)
	{
		if(arrayPointer[index] < pivot)
		{
			smallIndex++;
			swap(arrayPointer, smallIndex);
		}
	}
	swap(arrayPointer, value1Index, index);
	return smallIndex;
}


void threeSorts::qSort()
{
	int pivotLocation;
	if(value1Index < value2Index)
	{
		pivotLocation = partition(arrayPointer, value1Index, value2Index);
		qSort(list, value1Index, pivotLocation-1);
		qSort(list, pivotLocation+1, value2Index);
	}
}


My main file:
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
 
#include "threeSorts.h"
#include <cstdlib>

int main()
{		//declare 3 objects of the threeSorts class to test the 3 different
		//sorts. In each case we instantiate the object by calling
		//its constructor which creates an object with an array of 
//10 elements 
	threeSorts theBArray(10);
	threeSorts theSArray(10);
	threeSorts theIArray(10);
	int randomNum = 0;
		
		//use the rand function to generate random 
		//integers between 0 and 99 to fill the arrays
	for (int loop = 0; loop<10; loop++)	{
		randomNum = (rand()%100)+1;
		theBArray.insert(randomNum);
		theSArray.insert(randomNum);
		theIArray.insert(randomNum);
	}	
	cout << "Bubble Sort" << endl;
	cout << "***********" << endl;

	cout << "The numbers in the array are:" << endl;
	theBArray.display();

	theBArray.bSort();

	cout << "The numbers in the array after sorting are:" << endl;
	theBArray.display();


	cout << "Selection Sort" << endl;
	cout << "**************" << endl;

	cout << "The numbers in the array are:" << endl;
	theSArray.display();

	theSArray.sSort();

	cout << "The numbers in the array after sorting are:" << endl;
	theSArray.display();

	cout << "Insertion Sort" << endl;
	cout << "**************" << endl;

	cout << "The numbers in the array are:" << endl;
	theIArray.display();

	theIArray.iSort();

	cout << "The numbers in the array after sorting are:" << endl;
	theIArray.display();

	return 0;

}


Thanks in advance for anyone that can help, it's part of my coursework. I'm sure it's something stupid as always but my brain is wrecked!
antoin (7)
The errors I receive with this program are:

1>c:\users\antoin\documents\2nd year stuff\c++\cpp\projects\lab7\lab7\threesorts.cpp(129) : error C2065: 'index' : undeclared identifier

1>c:\users\antoin\documents\2nd year stuff\c++\cpp\projects\lab7\lab7\threesorts.cpp(137) : error C2065: 'value1Index' : undeclared identifier

1>c:\users\antoin\documents\2nd year stuff\c++\cpp\projects\lab7\lab7\threesorts.cpp(137) : error C2065: 'value2Index' : undeclared identifier

1>c:\users\antoin\documents\2nd year stuff\c++\cpp\projects\lab7\lab7\threesorts.cpp(140) : error C2065: 'list' : undeclared identifier

All undeclared identifier errors.
gzero (82)
You need to go study the concept of scope. When a variable is declared, it exists only for objects/functions within the same scope, or a sub-scope. For example: 
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
 
int partition(int* arrayPointer, int value1Index, int value2Index)       //Here, value1Index and value2Index exist only as long as the function call to partition does, and is only accessible from INSIDE partition.
{
	int pivot;
	int smallIndex;
	pivot = arrayPointer[value1Index];
	smallIndex = value1Index;

	for(int index = value1Index+1; index<=value2Index; index++)  //Here, the lifespan of index is only for the duration of the for loop.  Once you move beyond the for loop, it vanishes.
	{
		if(arrayPointer[index] < pivot)
		{
			smallIndex++;
			swap(arrayPointer, smallIndex);
		}
	}
	swap(arrayPointer, value1Index, index);  //That's why this returns an error saying value1Index and index are undeclared.
	return smallIndex;
}


void threeSorts::qSort()
{
	int pivotLocation;
	if(value1Index < value2Index)  //value1Index and value2Index don't exist within this scope.
	{
		pivotLocation = partition(arrayPointer, value1Index, value2Index);
		qSort(list, value1Index, pivotLocation-1);  //Since I'm just skimming your code, I don't see anywhere else where list is declared, but the problem is likely the same as above.
		qSort(list, pivotLocation+1, value2Index);
	}
}


If you want those variables to be accessible throughout every function within the class threeSorts, then you can declare them in your header file. (Make sure you clear out any re-definitions, such as the declaration of index within the for loop inside of partition.) One other thing to note is that you didn't declare partition properly. It should be:

int threeSorts::partition(int* arrayPointer, int value1Index, int value2Index)

A couple other things to note: You've declared the swap function to take three arguments, but then you only pass 2 arguments to it in partition. Also, in qsort you've declared qsort as not taking any arguments, but then you have it trying to pass arguments to itself. Those mistakes will give you compiler errors.

I hope this helps.
antoin (7)
Okay gzero, thanks mate got it working now with no errors
Topic archived. No new replies allowed.