R is considered the predominant language for data scientist and statisticians. Learn how to use R for your own data science projects.

I found this code on the internet and kinda need some explanation.

Keep in mind im a little new to c++.

Doesnt there need to be a partition point somewhere in here? If so how can I chose what i want it to be? (ex. middle, last, first item). Also what is static?? If you have a different version or know a good page to look at pleast let me know. Here is the code.

void QuickSort(itemType a[], indexType l, indexType r)

{

static itemType m;

static indexType j;

indexType i;

if(r > l) {

m = a[r]; i = l-1; j = r;

for(;;) {

while(a[++i] < m);

while(a[--j] > m);

if(i >= j) break;

std::swap(a[i], a[j]);

}

std::swap(a[i],a[r]);

QuickSort(a,l,i-1);

QuickSort(a,i+1,r);

}

}

Keep in mind im a little new to c++.

Doesnt there need to be a partition point somewhere in here? If so how can I chose what i want it to be? (ex. middle, last, first item). Also what is static?? If you have a different version or know a good page to look at pleast let me know. Here is the code.

void QuickSort(itemType a[], indexType l, indexType r)

{

static itemType m;

static indexType j;

indexType i;

if(r > l) {

m = a[r]; i = l-1; j = r;

for(;;) {

while(a[++i] < m);

while(a[--j] > m);

if(i >= j) break;

std::swap(a[i], a[j]);

}

std::swap(a[i],a[r]);

QuickSort(a,l,i-1);

QuickSort(a,i+1,r);

}

}

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialThanks for the reply.

Yes this is a learning experience, well somewhat. Basically I have to have the quicksort code in my program, rather than use the STL library. Basically what I am wanting to do is use two different versions of quicksort, one that runs using the last value as the pivot, and one that uses the middle value as the pivot.

The code I posted above seemed different and more concise than other versions I have seen where there are seperate "partition" functions. Such as this example:

template <class T>

void quickSort(T *a, int first, int last) {

if(first < last) {

int loc = partition(a, first, last);

quickSort(a, first, loc - 1);

quickSort(a, loc + 1, last);

}

}

template <class T>

int partition(T *a, int first, int last) {

int i = first;

int loc = last + 1;

T pivot = a[first];

while(i < loc) {

do {

++i;

} while((a[i] < pivot) && (i < last));

do {

--loc;

} while(a[loc] > pivot);

if(i < loc)

swap(a[i], a[loc]);

}

swap(a[first], a[loc]);

return(loc);

}

I guess im not really sure how to define what needs to be used as the pivot? I'm trying to compare the two seperate versions of quicksort using different pivots.

>> seperate "partition" functions.

I think you will find that the reason for that is that the function you posted is recursive.

>> QuickSort(a,l,i-1);

>> QuickSort(a,i+1,r);

Notice that these two calls to function QuickSort are made from within function Quicksort. Also notice that one call subtracts from i and the other increments i. This would indicate, at least to me, that i is the pivot point. that the first call handles the left partition and that the second call handles the right partition.

Here's an example of a recursive function that reverses a string,

#include <iostream>

#include <iomanip>

#include <string>

using namespace std;

template <class T>

void swap( T &op1, T &op2 )

{

T temp = op1;

op1 = op2;

op2 = temp;

}

template <class T>

void reverse( T op1, T op2 )

{

swap( *op1, *op2 );

if( op1 != op2 )

reverse( ++op1, --op2 );

}

int main()

{

string name = "Exceter";

reverse( name.begin(), name.end() - 1 );

cout << name << endl;

return 0;

}

-- output --

retecxE

Cheers!

Exceter

That would be my surmise, have you tested them? If the output is the same I would consider that ample evidence that they do the same thing.

If you want, you can even check their output against C's qsort function.

Exceter

If not I guess I dont understand what the arguments "l" and "r" are?

Points inscreased.

void QuickSort(itemType a[], indexType l, indexType r)

{

static itemType m;

static indexType j;

indexType i;

if(r > l) {

m = a[r]; i = l-1; j = r;

for(;;) {

while(a[++i] < m);

while(a[--j] > m);

if(i >= j) break;

std::swap(a[i], a[j]);

}

std::swap(a[i],a[r]);

QuickSort(a,l,i-1);

QuickSort(a,i+1,r);

}

}

Well, to tell you the truth, the code doesn't say. :-)

However, I'd say that indexType is nothing more than a macro, because if it was a template there would be a template declaration above the function, indicating what type to use for the index. In like manner itemType would be a macro for the data type of the array that is being sorted. These would look like this, for example,

#define indexType int

#define itemType int

However, I'd convert the function so it used templates. For example,

template <class T, class TT>

void QuickSort( T a[], TT l, TT r)

{

static T m;

static TT j;

TT i;

if(r > l)

{

m = a[r]; i = l-1; j = r;

for(;;)

{

while(a[++i] < m);

while(a[--j] > m);

if(i >= j) break;

std::swap(a[i], a[j]);

}

std::swap(a[i],a[r]);

QuickSort(a,l,i-1);

QuickSort(a,i+1,r);

}

}

...

int arr[] = { 32, 56, 112, 9, -45, 12, 3, 99 };

QuickSort( arr, 0, 7 );

-- result --

-45 3 9 12 32 56 99 112

Exceter

A pointer to the data,

The first index,

The last index

For example, if you used the other function to sort this, using the exact same parameters, it would do the same thing. For example,

int arr[] = { 32, 56, 112, 9, -45, 12, 3, 99 };

quickSort( arr, 0, 7 );

-- result --

-45 3 9 12 32 56 99 112

Exceter

C++

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

Try this link,

http://www.cise.ufl.edu/~ddd/cis3020/summer-97/lectures/lec17/sld003.htm

>> If you have a different version or know a good page to look at pleast let me know.

Well, I don't have a different version, I don't need one, because the C standard library defines the qsort function and the C++ STL standard library defines the sort function. Therefore, unless this is a learning excersise you are much farther ahead using them.

>> Also what is static??

The static keyword has different meanings depending on the context in which it is used. In this case, it means that these variables are not destoryed when the function terminates and, consequently, retain their values from one function call to the next. Implicitly, this means that there is only one copy of these variables and new instances are not re-created when another function call is made. variables m and j. You can think of them as global variables that are only accessible from within the function QuickSort.

Cheers!

Exceter