4 Replies - 2339 Views - Last Post: 24 October 2012 - 08:47 AM Rate Topic: -----

#1 mgrex  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 182
  • Joined: 25-March 10

Selection sort refuses to work properly.

Posted 22 October 2012 - 05:08 PM

Int main's Line 76, is function call to the selection sort function in SearchableVector.h.

SelectionSort, fails to be called unless line 60 is specified with the following: SearchableVector<int> intTable2(1);
A 1 (or any number greater than zero) must be in the argument. May someone please tell me how to get the function to worth without having to result to this modification?

Without the modification, the message is dislayed: Error subscript out of range.

Out another note, even with the said modification, the selection sort, fails to display the contents in order.
The following:
	intTable2.push_back(5);
	intTable2.push_back(3);
	intTable2.push_back(2);
	intTable2.push_back(1);
	intTable2.push_back(6);
	intTable2.push_back(15);
	intTable2.push_back(7);


Is displayed as, 0 5 5 5 5 6 15 15

int main()
// This program demonstrates the SearchableVector template . 
#include <iostream> 
#include "SearchableVector.h" 
using namespace std; 

int main() 
{
	const int SIZE = 10;		// Number of elements 
	int count;					// Loop counter 
	int result;					// To hold search results

	// Create 2 SearchableVector objects 
	SearchableVector<int> intTable(SIZE); 
	SearchableVector<double> doubleTable(SIZE); 
	
	// Store values in objects. 
	for (count = 0; count < SIZE; count++) 
	{ 
		intTable[count] = (count * 2); 
		doubleTable[count] = (count * 2.14); 
	} 

	// Display the values in the objects . 
	cout << "These values are in int Table:\n"; 
	for (count = 0; count < SIZE; count++) 
		{cout << intTable[count] << " "; }
	cout << endl << endl; 
	
	cout << "These values are in doubleTable:\n"; 
	for (count = 0; count < SIZE; count++) 
		cout << doubleTable [count] << " "; 
	cout << endl; 
	

	// Search for the value 6 in intTable . 
	cout << "\nSearching for 6 in intTable.\n"; 
	result = intTable.findItem(6); 
	if (result == -1) 
		cout << "6 was not found in intTable.\n"; 
	else 
		cout << "6 was found at subscript " << result << endl; 	 

	// Search for the value 12.84 in doubleTable. 
	cout << "\nSearching for 12.84 in doubleTable.\n" ; 
	result = doubleTable.findItem(12.84); 
	if (result == -1) 
		cout<< "12.84 was not found in doubleTable.\n"; 
	else 
		cout << "12.84 was found at subscript " << result << endl; 

	// Search for the value 12.85 in doubleTable. 
	cout << "\nSearching for 12.85 in doubleTable.\n" ; 
	result = doubleTable.findItem(12.85); 
	if (result == -1) 
		cout<< "12.85 was not found in doubleTable.\n"; 
	else 
		cout << "12.85 was found at subscript " << result << endl; 


	SearchableVector<int> intTable2(0);	//must be intTable2(7) for line 78 to display

	intTable2.push_back(5);
	intTable2.push_back(3);
	intTable2.push_back(2);
	intTable2.push_back(1);
	intTable2.push_back(6);
	intTable2.push_back(15);
	intTable2.push_back(7);

	for (count = 0; count < intTable2.getVecSize(); count++) 
		cout << "->" << intTable2[count]; 
	cout << endl; 

	cout << "ok \n....\n";

	intTable2.selectionSort();	//culprit;
	
	for (count = 0; count < intTable2.getVecSize(); count++) 
		cout << "->" << intTable2[count]; 
	cout << endl; 
	cout << "\nThis DID NOT displayed, with the 3 previous lines commented out.\n";
	
	system("pause");
	return 0;
}



SearchableVector.h derived class
//Applying class templates to an inherited class

#ifndef SEARCHABLEVECTOR_H 
#define SEARCHABLEVECTOR_H 
#include "SimpleVector.h"

template <class T> 
//**********************************************************
// Each time the name SimpleVector is used in the class template,
// the type, parameter T is used with it.
class SearchableVector : public SimpleVector<T> 
{ 
public : 
	//*******************************************
	// Default constructor
	// <T>, the type parameter, must be passed, 
	// since SimpleVector, is a class template.
	SearchableVector() : SimpleVector<T>() 
		{ } 

	// Constructor 
	SearchableVector(int size) : SimpleVector<T>(size) 
		{ } 

	// Copy constructor
	SearchableVector(const SearchableVector &); 

	//***************************************************************************
	// Accessor to find an item
	// Accepts an argument, and performs a simple linear search to determine
	// whether the argument's value is stored in the array. If the value is 
	// found in the array, its subscript is returned. Otherwise, -1 is returned. 
	int findItem(const T); 
	void selectionSort();//T array[], int size) 
};

//****************************************************** 
// Copy constructor 
//****************************************************** 
template <class T> 
SearchableVector<T>::SearchableVector(const SearchableVector &obj) : SimpleVector<T>(obj.size())
{ 
	for(int count = 0; count < this->size(); count++) 
		this->operator[](count) = obj[count]; 
} 

//****************************************************** 
// findItem function 
// This function searches for item. If item is found 
// the subscript is returned. Otherwise -1 is returned. 
//****************************************************** 
/*template <class T> 
int SearchableVector<T>::findItem(const T item) 
{ 
	for (int count = 0; count <= this->size(); count++) 
	{
		if (getElementAt(count) == item) 
			return count; 
	}
	return -1;
}*/

template <class T> 
int SearchableVector<T>::findItem(T item) 
{ 
	//From Pr08_02, a linear search
	/*int first = 0,					// First array element 
	last = size() - 1,				// Last a rray element 
	middle,							// Midpoint of search 
	//position = -1 ; 				// position of search value 
	bool found = false;

	while (!found && first <= last) 
	{ 
		middle = (first + last) / 2; 	// Calculate midpoint 
		if (getElementAt[middle] == item)		// If value is found at mid		<<----Wrong
		{ 
			found = true; 
			position = middle; 
		}
		else if (getElementAt[middle] > value) // If value is in lower half 
			last = middle - 1; 
		else 
			first = middle + 1;			// If value is in upper half 
	}*/

	T first = 0,
		last = size(),
		middle = 0,
		position = -1;

	while ((SimpleVector<T>::operator[](middle) != item) && (first <= last))
	{
		middle = (first + last) / 2;
		if (SimpleVector<T>::operator[](middle) == item)
		{
			position = middle;
		}
		else if (SimpleVector<T>::operator[](middle) > item)	//value is in lower half
			last = middle - 1;
		else													//in upper half
			first = middle + 1;
	}

	middle = (first + last) / 2;
	
	if (first <= last)
		return middle; 
	else
		return -1;

	//Alternative format

	/*int middle = 0,
		//comparisonCount = 1,
		lowerBound = 0,
		upperBound = size();

	middle = (lowerBound + upperBound) / 2;

	while ((SimpleVector<T>::operator[](middle) != item) && (lowerBound <= upperBound))
	{
		//comparisonCount++;
		
		if (SimpleVector<T>::operator[](middle) > item)
			upperBound = middle - 1;
		else
			lowerBound = middle + 1;

		middle = (lowerBound + upperBound) / 2;
	}

	if (lowerBound <= upperBound)
		return middle; 
	else
		return -1;*/
}

template <class T> 

void SearchableVector<T>::selectionSort() 
{ 
	T startScan, minIndex, minValue; 
	for (startScan = 0; startScan < (getVecSize() - 1); startScan++) 
	{ 
		minIndex = startScan; 
		minValue = SimpleVector<T>::operator[](startScan); //array[startScan]; 
		for(int index = startScan + 1; index < getVecSize(); index++) 
		{ 
			if (SimpleVector<T>::operator[](index) < minValue) 
			{ 
				minValue = SimpleVector<T>::operator[](index); 
				minIndex = index; 

				//array[minIndex] = array[startScan]; 
				SimpleVector<T>::operator[](minIndex) = SimpleVector<T>::operator[](startScan);
				//array[startScan] = minValue; 
				SimpleVector<T>::operator[](startScan) = SimpleVector<T>::operator[](minValue);
			} 
		}
	} 
} 

#endif 



SimpleVector.h base class
// SimpleVector class template declaration. Throughout the class declaration,
// the data type paramerer is used where you wish to support any data type.
// Benefit of doing a class template, is that we don't have to creater multiple classes
// for different primitive data types, that would perform error/bounds checking for 
// each of them.

#ifndef SIMPLEVECTOR_H 
#define SIMPLEVECTOR_H 
#include <iostream>		// Needed for bad_alloe exception 
#include <new>			// Needed for the exit function 
#include <cstdlib> 
using namespace std; 

template <class T> 
class SimpleVector 
{ 
private: 
	T *aptr;				// To point to the allocated array
	
	//*****************************************************************
	// arraySize member variable is declared as an int. This is because
	// it holds the size of the array, which will be an integer value, 
	// regardless of the data type of the array. This is also why 
	// the size member function returns an int.
	//*****************************************************************
	int	 arraySize;			// Number of elements in the array

	void memError();		// Handles memory allocation errors 
	void subError();		// Handles subscripts out of range

public: 
	// Default constructor 
	SimpleVector() 
		{	aptr = 0; arraySize = 0;	} 

	// Constructor declaration 
	SimpleVector(int);

	// Copy constructor declaration 
	SimpleVector(const SimpleVector &); 

	// Destructor declaration 
	~SimpleVector(); 


	// Accessor to return the array size 
	int size() const 
		{	return arraySize;	} 

	// Accessor to return a specific element 
	T getElementAt(int position); 

	// Overloaded [] operator declaration 
	T &operator[](const int &); 

	int getVecSize()
	{	return arraySize;	}

	void push_back(const T &);
	void pop_back ();
}; 
 

//************************************************************
// Constructor for SimpleVector class. Sets the size of the  
// array and allocates memory for it. 
//************************************************************ 
template <class T> 
SimpleVector<T>::SimpleVector(int s) 
{ 
	arraySize = s; 
	// Allocote memory for the array. 
	try 
	{ 
		aptr = new T [s]; 
	}
	catch (bad_alloc) 
	{ 
		memError(); 
	} 
	
	// Initialize the array . 
	for (int count = 0; count < arraySize; count++) 
		*(aptr + count) = 0;
}

//*********************************************
// Copy Constructor for SimpleVector class. 
//********************************************* 
template <class T> 
SimpleVector<T>::SimpleVector(const SimpleVector &obj) 
{ 
	// Copy the array size. 
	arraySize = obj.arraySize; 

	// Allocate memory for the array. 
	aptr = new T[arraySize]; 
	if (aptr == 0) 
		memError(); 

	// Copy the elements of obj's array. 
	for(int count = 0; count < arraySize; count++) 
		*(aptr + count) = *(obj.aptr + count); 
}

//***************************************
// DestrUCtor for SimpleVector class. 
//***************************************
template <class T> 
SimpleVector<T>::~SimpleVector() 
{ 
	if (arraySize > 0) 
		delete [] aptr; 
} 

//************************************************************
// memError function. Displays an error message and
// terminates the program when memory allocation fails.
//************************************************************
template <class T> 
void SimpleVector<T>::memError() 
{ 
	cout << "ERROR:Cannot allocate memory.\n"; 
	exit(EXIT_FAILURE); 
} 

//************************************************************
// subError function. Displays an error message and 
// terminates the program when a subscript is out of range.
//************************************************************
template <class T> 
void SimpleVector<T>::subError() 
{  
	cout << "ERROR: Subscript out of range.\n";
	system("pause");
	exit(EXIT_FAILURE); 
}

//*****************************************************
// getElementAt function. The argument is a subscript. 
// This function returns the value stored at the sub-
// cript in the array.
//*****************************************************
template <class T> 
T SimpleVector<T>::getElementAt(int sub) 
{
	if (sub < 0 || sub >= arraySize) 
		subError(); 
	return aptr[sub]; 
} 

//********************************************************* 
// Overloaded [] operator. The argument is a subscript. 
// This function returns a reference to the element  
// in the array indexed by the subscript.  
//*********************************************************
template <class T> 
T &SimpleVector<T>::operator[](const int &sub) 
{ 
	if (sub < 0 || sub >= arraySize) 
		subError(); 
	return aptr[sub]; 
}

template <class T> 
void SimpleVector<T>::push_back(const T &num) 
{ 
	//cout << "\narray size before: " << arraySize << endl;
	T *temp = new T[arraySize + 1];
		
	for(int index = 0; index < arraySize; index++)	// if arraySize == 0, this will not execute.
	{
		temp[index] = aptr[index];
	}
	
	
	temp[arraySize++] = num;	// the folloaing is wrong: temp[arraySize+1] = num
	
	//delete [] aptr;
	aptr = temp;
	//cout << "\narray size after: " << arraySize << endl;
} 

template <class T>
void SimpleVector<T>::pop_back()
{
	T *temp = new T[arraySize];

	for (int index = 0; index < arraySize; index++)
	{
		temp[index] = aptr[index];
	}

	temp[arraySize--];
	//delete [] aptr;

	aptr = temp;	
}


#endif 

This post has been edited by mgrex: 22 October 2012 - 06:54 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Selection sort refuses to work properly.

#2 jimblumberg  Icon User is online

  • member icon


Reputation: 3993
  • View blog
  • Posts: 12,321
  • Joined: 25-December 09

Re: Selection sort refuses to work properly.

Posted 22 October 2012 - 07:57 PM

Have you tried running this program through your debugger. Single step through your selection sort function and watch what is happening.

My next suggestion would be to get your selection sort working using a std::vector, or array of one type, remove all the template crap until you have this working correctly. Just create a main() that populates a vector or array, prints this vector or array before and after a call to your sort routine. Once you get your sort working correctly you can then convert to a template class.

Jim

This post has been edited by jimblumberg: 22 October 2012 - 07:57 PM

Was This Post Helpful? 0
  • +
  • -

#3 mgrex  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 182
  • Joined: 25-March 10

Re: Selection sort refuses to work properly.

Posted 24 October 2012 - 07:33 AM

I googled on a debugging turoial, and I couldn't find a proper one, for Visual C++ 2010.
https://www.google.c...c.1.LjZBNUpwy3I

This was worthless: http://kipirvine.com...o2010/index.htm

BTW, the array index was able to be arranged in order by changing Line 143 in SearchableVector.h, from T, to int type.
	int startScan, minIndex; 
	T minValue; 


But instead of 1 2 3 5 6 7 15
Output is 0 5 5 5 5 6 15 15

This post has been edited by mgrex: 24 October 2012 - 07:55 AM

Was This Post Helpful? 0
  • +
  • -

#4 jimblumberg  Icon User is online

  • member icon


Reputation: 3993
  • View blog
  • Posts: 12,321
  • Joined: 25-December 09

Re: Selection sort refuses to work properly.

Posted 24 October 2012 - 07:51 AM

Have you tried "debugging with visual studio 2010", instead of "visual studio 2010 display debugger" sometimes you need to rearrange search terms in Google to get valid hits. The first two links in the above link seem to be fairly decent.


Jim
Was This Post Helpful? 0
  • +
  • -

#5 mgrex  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 182
  • Joined: 25-March 10

Re: Selection sort refuses to work properly.

Posted 24 October 2012 - 08:47 AM

The most I've learned from googling "Debugging", is how to use breakpoints, which has been of no use so far.

http://weblogs.asp.n...tudio-2010.aspx

Edit: Weird, it seems, the program works now, by slightly modifying the sort algorithm.

This post has been edited by mgrex: 24 October 2012 - 09:16 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1