?
Solved

Quicksort questions, function included

Posted on 2003-10-26
8
Medium Priority
?
406 Views
Last Modified: 2010-04-01
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);
  }
}
0
Comment
Question by:killer455
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 3
8 Comments
 
LVL 8

Accepted Solution

by:
Exceter earned 240 total points
ID: 9624799
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).

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
0
 

Author Comment

by:killer455
ID: 9629789
Exceter,

Thanks 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.


0
 
LVL 8

Expert Comment

by:Exceter
ID: 9631141
>> The code I posted above seemed different and more concise than other versions I have seen where there are
>> 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
0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 

Author Comment

by:killer455
ID: 9631813
So basically both quicksorts I posted do the exact same thing?

0
 
LVL 8

Expert Comment

by:Exceter
ID: 9634375
So basically both quicksorts I posted do the exact same thing?

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
0
 

Author Comment

by:killer455
ID: 9637204
What exactly is the indexType?? Shouldnt it always be an int since its an index in the array?
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);
  }
}
0
 
LVL 8

Expert Comment

by:Exceter
ID: 9639719
>> What exactly is the indexType??

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
0
 
LVL 8

Expert Comment

by:Exceter
ID: 9639733
Note: the arguments for both of these quicksort routines are as follows,

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
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
Suggested Courses

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question