[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 410
  • Last Modified:

Quicksort questions, function included

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
killer455
Asked:
killer455
  • 5
  • 3
1 Solution
 
ExceterCommented:
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
 
killer455Author Commented:
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
 
ExceterCommented:
>> 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.

 
killer455Author Commented:
So basically both quicksorts I posted do the exact same thing?

0
 
ExceterCommented:
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
 
killer455Author Commented:
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
 
ExceterCommented:
>> 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
 
ExceterCommented:
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

[Webinar] Cloud and Mobile-First Strategy

Maybe you’ve fully adopted the cloud since the beginning. Or maybe you started with on-prem resources but are pursuing a “cloud and mobile first” strategy. Getting to that end state has its challenges. Discover how to build out a 100% cloud and mobile IT strategy in this webinar.

  • 5
  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now