Solved

Quicksort questions, function included

Posted on 2003-10-26
8
397 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
  • 5
  • 3
8 Comments
 
LVL 8

Accepted Solution

by:
Exceter earned 60 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
 

Author Comment

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

0
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
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

What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
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…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

747 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

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now