w*******s
发帖数: 96 | 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 (a
if (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 <
for (int i = 0; i
{
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");
} | w*******s
发帖数: 96 | 2 貌似与编译器有关。在G++下面运行没有问题，在VC下报异常。
【在 w*******s 的大作中提到】
: 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)
| v***a
发帖数: 365 | 3
Maybe here:
int pivot = 0;
if (d < v[low].length())
pivot = v[low][d];
【在 w*******s 的大作中提到】
: 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)
|
|
