到家了，报个平安# pets - 心有所宠
w*s
1 楼
If the string is not the same length, my code will crash because of array
index out of boundary. Can you help find the bug?
//Refer Algorithm 4th, page 722
void exch(string &a, string &b)
{
string c = a;
a = b;
b = c;
}
int compare(int a, int b)
{
if (aif (a==b) return 0;
if (a>b) return 1;
}
void ThreeWayQsort(vector &v, int low, int high, int d)
{
if (high<=low) return;
//3 way partition to handle duplicate
int lt = low;
int gt = high;
int i = low + 1;
int pivot = v[low][d];
while (i <= gt)
{
if (d>= v[i].size()) {exch(v[i++],v[lt++]);continue;}
int cmp = compare(v[i][d], pivot);
if (cmp < 0) {
exch(v[i++],v[lt++]);
}else if (cmp > 0 ){
exch(v[i],v[gt--]);
}else{
i++;
}
}
// now divide and conqured.
ThreeWayQsort(v,low,lt-1,d);
if (pivot>0) { ThreeWayQsort(v,lt,gt,d+1);}; //recursive here.
ThreeWayQsort(v,gt+1,high,d);
}
void sort(vector &v)
{
int len = v.size();
ThreeWayQsort(v, 0, len-1, 0);
}
void printV(vector &v, string str)
{
cout << str <
cout << i << ":" << v[i] << endl;
}
}
void ThreeWaySortTestMain()
{
vector v;
v.push_back("she");
v.push_back("sells");
v.push_back("seashells");
v.push_back("by");
v.push_back("the");
v.push_back("sea");
v.push_back("shore");
v.push_back("the");
v.push_back("shells");
v.push_back("she");
v.push_back("sells");
v.push_back("are");
v.push_back("surely");
v.push_back("seashells");
printV(v, "before sort");
sort(v);
printV(v,"after sort");
}
index out of boundary. Can you help find the bug?
//Refer Algorithm 4th, page 722
void exch(string &a, string &b)
{
string c = a;
a = b;
b = c;
}
int compare(int a, int b)
{
if (aif (a==b) return 0;
if (a>b) return 1;
}
void ThreeWayQsort(vector
{
if (high<=low) return;
//3 way partition to handle duplicate
int lt = low;
int gt = high;
int i = low + 1;
int pivot = v[low][d];
while (i <= gt)
{
if (d>= v[i].size()) {exch(v[i++],v[lt++]);continue;}
int cmp = compare(v[i][d], pivot);
if (cmp < 0) {
exch(v[i++],v[lt++]);
}else if (cmp > 0 ){
exch(v[i],v[gt--]);
}else{
i++;
}
}
// now divide and conqured.
ThreeWayQsort(v,low,lt-1,d);
if (pivot>0) { ThreeWayQsort(v,lt,gt,d+1);}; //recursive here.
ThreeWayQsort(v,gt+1,high,d);
}
void sort(vector
{
int len = v.size();
ThreeWayQsort(v, 0, len-1, 0);
}
void printV(vector
{
cout << str <
cout << i << ":" << v[i] << endl;
}
}
void ThreeWaySortTestMain()
{
vector
v.push_back("she");
v.push_back("sells");
v.push_back("seashells");
v.push_back("by");
v.push_back("the");
v.push_back("sea");
v.push_back("shore");
v.push_back("the");
v.push_back("shells");
v.push_back("she");
v.push_back("sells");
v.push_back("are");
v.push_back("surely");
v.push_back("seashells");
printV(v, "before sort");
sort(v);
printV(v,"after sort");
}
