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.
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.
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];
}
}