Quicksort

[edmund1978]

I'm trying to adapt a quicksort class from sorting arrays to sorting vectors. I've used this for arrays, and it works (was taken from textbook) but I get a memory error when I try it with vectors. Any ideas?

#include <vector>
using std::vector;

class myQuickSort
{
public:
void sortArray(vector<int> a, int i, int j);
inline void exchange(vector<int> b, int i, int j);
int partition(vector<int> a, int low, int high);
};

void myQuickSort::sortArray(vector<int> a, int i, int j)
{
//int partition(int a[], int, int);
if (i >= j || i < 0)
return;
int k = partition(a, i, j);
sortArray(a, i, k-1);
sortArray(a, k+1, j);
}

int myQuickSort:artition(vector<int> a, int low, int high)
{
register int pe;
//int pe;
int i = low;
int j = high;

exchange(a, (i+j)/2, j);
pe = a[j];
while (i < j)
{
while (i<j && a <= pe) i++;
while (i<j && a[j] >= pe) j--;
if (i<j) exchange(a, i++, j);
}
if (i != high) exchange(a,i,high);
return i;
}

inline void myQuickSort::exchange(vector<int> b, int i, int j)
{
int t = b[j];
b[j] = b;
b = t;
}

 

[edmund1978]

myQuickSort mySort;
mySort.sortArray(partitionsVector, 0, 40);

the above is the code used to call the function. It says 'Debug error!' 'Damage after normal block (#737) at 0x.......... (memory location). This is how I ran it when using arrays also, which worked

 

[edmund1978]

Is it because of statements such as these:
b[j] = b;
b = t;
(where b is a vector of ints and t is an int
Are these legal assignments for vectors.

 

[palbano]

> Is it because of statements such as these:

Yes, for instance:

> while (i<j && a <= pe) i++;

When I compile your source on VC 6 W2K it does not even compile. Here is the error message:


error C2678: binary '<=' : no operator defined which takes a left-hand operand of type 'class std::vector<int,class std::allocator<int> >' (or there is no acceptable conversion)

There is no operator <= for a vector, also it just does not make any sense in the context of your solution. I don't know why you can even compile the code, let alone run it.

-pete

 

[edmund1978]

Sorry something must have messed up when I copied and pasted, that function reads as follows (with a as opposed to a in the while loop). Does compile, but simply crashes with memory error when it is called the same way when it was used with arrays.

int myQuickSort:artition(vector<int> a, int low, int high)
{
register int pe;
//int pe;
int i = low;
int j = high;

exchange(a, (i+j)/2, j);
pe = a[j];
while (i < j)
{
while (i<j && a <= pe) i++;
while (i<j && a[j] >= pe) j--;
if (i<j) exchange(a, i++, j);
}
if (i != high) exchange(a,i,high);
return i;
}

 

[edmund1978]

I don't believe it, it did it again, the first is supposed to read a [ i ] . a with i in square brackets after it.

 

[edmund1978]

first while loop that is

 

[edmund1978]

also last statement in the exchange function should read b [ i ] = t ;

 

[palbano]

Yeah, don't use an 'i' inside array brackets, tek-tips sees it as TGML, or uncheck the 'Process TGML' box at the bottom of the message edit box.

Ok, so I fixed all the TGML problems then I added the following main and ran it:


void main(){
vector<int> v;
v.push_back( 7);
v.push_back( 5);
v.push_back( 10);
v.push_back( 3);
myQuickSort qs;
qs.sortArray( v, 0, 3);

for(int j=0; j<v.size(); j++)
cout << v[j] << &quot;,&quot;;

cout << endl;
cout << &quot;enter to exit...&quot;;
int n;
cin >> n;

}


Results:
1) I do not get any memory errors.
2) I do not get a sorted vector.

Of course to actually get the sorted vector you need to change all of your class functions to take a 'reference' to the vector. After I did that it works correctly

void sortArray(vector<int>& a, int i, int j);
inline void exchange(vector<int>& b, int i, int j);
int partition(vector<int>& a, int low, int high);


One other point. You may want to consider that only the 'sortArray' function should be public.

Hope this helps
-pete