Sort Machine

A.First Edition
This is my first edition of a sort machine which is a class doing both trimming and sorting of a string.
B.The problem
Write a function to sort a character string in ascending alphabetic order.

The function should also convert all lower case letter to upper case letter.

You should remove all characters that are not alphabetic (i.e. take out spaces,

numbers, and punctuation).

The function must receive a pointer to the string, and return a pointer to

the string. Recall that strings end in '\0' and you should not sort this character.

For example the string "This is a string!", should be sorted as "AGHIIINRSSSTT".

(Hint: You can use the bubble sort algorithm.)

Write a driver program to test your function.
กก
C.The idea of program
There are two major feature about my class as mentioned in the remark part of my program:
1. I made the storage of string flexible by implementing it like dynamic array so that it can increase length
according to input. I defined constant "MaxLength" for class which must be passed in and initialized before
constructor. Then by record number of "relocating", I can increase one "MaxLength" every time my string found
out it need more memory. At destructor, the dynamic allocated memory is freed.
2. I made several flags for my class so that programmer can choose different sorting algorithms like bubble
sort, quick sort etc. and sorting type as ascending or descending. 
D.The major functions
1. char* SortMachine::trimStr(const char* const str)
It first trims off all other char except letters, also make all them big cases. As the passing parameter str 
can not be changed in any way, I made both the contents and pointer itself const. During trimming, it checks
the length of input string, see if the length exceeds size of my array, a "relocate" is called by add more 
space to original array. So it is like the way of dynamic array.
2. SortMachine::SortMachine(const char* const str, int defaultLength)
This constructor with defaultLength which is used to initialize the constant "MaxLength".
C.Further improvement
1. add more sorting algorithms.  
2. make it more general so that any type of data can be sort, not only char.
กก
/***************************************************************************
////Author: Qingzhe Huang
////Date: Jul 13, 2003
////Name of program: Sorting Machine
///////////////////////////////////////////////////////////////////////////

I arbitarily made my program a class, as I see some opportunity that it is fairly 
a common job to do sorting for a string, plus some extra job like "trimming".
And what's more I made my string a kind of "dynamic" array which can increase 
length according input by "realloc" new length of mem to sting pointer.
Basically there two major features of my class:
	1. In my class, I set up several flag to enable it to sort in different algorithms, 
	like bubble sort, quick sort and maybe more in future. Also, I make it possible to
	sort it in both ascending and descending by open a method called "setParam" which 
	allow program to set all sorting parameters---sortType, isAscending, maybe more in
	future.
	2. For the trimming part, I made a my array like dynamic array so that it can increase 
	automatically realloc memory by adding  20 bytes more to old size. So, I defined a
	constant "MaxLength" and use the method introduced in lecture to initialize it 
	before constructor. A "relocCounter" to record how many times reloc is invoked, so
	by increment this counter, 20 more bytes are added to "reallocate" for string.
	And this 20bytes is passed by default in constructor to set the constant "MaxLength", 
	so it is also changeable by programmer.
	At destructor, the dynamic allocated memory is freed.
/////////////////////////////////////////////////////////////////////////////
////Possible improvement: 
// 1. add more sorting algorithms
// 2. make it more general so that any type of data can be sort,not only char
****************************************************************************/

#include <iostream>

using namespace std;

enum SortType
{BubbleSort, QuickSort};

class SortMachine
{
private:
	const int MaxLength; //default pre-allocate array length
	int relocCounter;//record number of reloc in case string length is longer than size
	char* myStr;
	bool ascending;  //default is ascending, however, you can set by setParam
	SortType sortType; //enum indicate bubbleSort or quickSort
	int size; //it is the size of mem alloc for str, not length, 
	int length;//this is indeed the length of myStr
	void doQuickSort(int start, int end);
	int partition(int start, int end); //I am not sure if it is better to put in protected
	void swap(int i, int j);//because like these functions should be deriveable in child class
	bool smaller(int i, int j);//this is an ackward method to implement descending 
	bool smallerEqual(int i, int j);
protected:
	//I put all initialize part here instead of constructor, simply because it is a painful
	//in c++ that you cannot control the constructor of parent class, they are always called
	//not like in Delphi,you can have fully control of ancestor's constructor
	//so, in this case, all derived class can have opportunity to modify the ancestor's
	//initialize method, where if put in constructor, you cannot do it.
	void initialize();
	//the passed parameter should not be changed either value or pointer itself
	char* trimStr(const char* const str);
	void relocStr();
	void quickSort();
	void bubbleSort();
public:
	SortMachine(int defaulLength = 20);
	SortMachine(const char* const str, int defaultLength =20);
	~SortMachine();
	void setStr(const char* const str);//it trims and assign to myStr
	void setParam(SortType mySortType = BubbleSort, bool isAscending = true);
	const char* getStr() { return myStr;}
	void sortStr();
};

int main()
{
	SortMachine s;
	char str[80];
	cin.getline(str, 80);
	s.setStr(str);
	s.setParam(QuickSort, false);
	s.sortStr();
	cout<<s.getStr()<<endl;

	return 0;
}

//this is put into protected as derived class may need to modify
void SortMachine::initialize()
{
	//it is absurd to use this name to represent how many times reloc happened, 
	relocCounter =0; 
	ascending = true;
	sortType = BubbleSort;
	size = 0;
	myStr = NULL;
}

//this constructor with only a default size of 
SortMachine::SortMachine(int defaultLength)
:MaxLength(defaultLength) //initialize constant in class
{
	initialize();
}

//the constructor with both input str and default length of my array
SortMachine::SortMachine(const char* const str, int defaultLength)
:MaxLength(defaultLength)//initialize constant in class
{
	initialize();
	myStr = trimStr(str);
}

//we need to free the memory what allocated
SortMachine::~SortMachine()
{
	free((void*)(myStr));
}

void SortMachine::setStr(const char* const str)
{
	myStr = trimStr(str);
}

//as the str is not supposed to be changed either contents or itself, I made const both ways
char* SortMachine::trimStr(const char* const str)
{
	int counter =0;
	char* target;
	char* source;

	//first make sure user is not naughty
	if (str==NULL)
	{
		return NULL;
	}
	//this is the default size of mystr
	size = MaxLength;//at first it is MaxLength
	myStr =(char*)malloc(size);

	target = myStr;
	source = (char*)str;

	while (*source!=NULL)
	{
		if (*source>='A'&&*source<='Z')//I prefer not to use ASCII number for compatible reason
		{
			*target = *source;
			target++;
			counter++;
			
			//this means we must reloc mem for myStr, as NULL is not write at end
			if (counter==size)			
			{
				relocStr();
				target = myStr+counter; //restore position of target
			}
		}
		else
		{
			if (*source>='a'&&*source<='z')//I prefer not to use ASCII number for compatible
			{
				*target = *source + 'A' - 'a';//it is better not use ASCII number
				target++;
				counter++;
				if (counter==size)			
				{
					relocStr();
					target = myStr+counter; //restore position of target
				}
			}
		}
		source++;//in any case, we move to next char
	}
	*target = NULL; //write last NULL at end.
	length = counter;
	return myStr;
}

void SortMachine::relocStr()
{
	char* temp;
	relocCounter++;
	size = (1+relocCounter)*MaxLength;
	//better to test before assign myStr, so, if exception, we didn't destroy what we have
	//I read this from some book
	temp = (char*)realloc((void*)(myStr), size);
	if (temp!=NULL)
	{
		myStr = temp;
	}
	else
	{
		cout<<"Fail to reloc!";
	}
}

void SortMachine::sortStr()
{
	switch (sortType)
	{
	case BubbleSort:
		bubbleSort();
		break;
	case QuickSort:
		quickSort();
		break;
	}
}

void SortMachine::setParam(SortType mySortType, bool isAscending)
{
	sortType = mySortType;
	ascending = isAscending;
}

void SortMachine::quickSort()
{
	doQuickSort(0, length-1);
}

void SortMachine::doQuickSort(int start, int end)
{
	int pos;
	if (start<end)
	{
		pos = partition(start, end);
		doQuickSort(start, pos-1);
		doQuickSort(pos+1, end);
	}
}

int SortMachine::partition(int start, int end)
{
//	char ch;
	int i;
	i = start-1;
//	ch = myStr[end];
	for (int j=start; j<end; j++)
	{
		//if (myStr[j]<=ch)
		if (smallerEqual(j, end))
		{
			i++;
			swap(i,j);		
		}
	}
	swap(i+1, j);
	return i+1;
}

void SortMachine::bubbleSort()
{	
	for (int i=0; i< length-1; i++)
	{
		for (int j=i+1; j<length; j++)
		{
			//if (myStr[i]>myStr[j])
			if (smaller(j, i))
			{
				//swap
				swap(i, j);
			}
		}
	}
}

void SortMachine::swap(int i, int j)
{
	char ch;
	if (i!=j)
	{
		ch = myStr[i];
		myStr[i] = myStr[j];
		myStr[j] = ch;
	}
}

//I made this to make descending sorting possible
bool SortMachine::smaller(int i, int j)
{
	if (ascending)
	{
		return myStr[i]<myStr[j];
	}
	else
	{
		return myStr[i]>=myStr[j];
	}
}

//I made this to make descending sorting possible
bool SortMachine::smallerEqual(int i, int j)
{
	if (ascending)
	{
		return myStr[i]<=myStr[j];
	}
	else
	{
		return myStr[i]>myStr[j];
	}
}







	

			


                                 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)

Hosted by www.Geocities.ws

1