CODEWITHSUNDEEP
c++algorithmquicksort
user200081
user200081

Reputation: 563

Comparison of equal values in Quicksort

I have an object that has three variables in it: a source vertex, a destination vertex, and a length. I have a Quicksort Algorithm that sorts an object by its length. However, I want it so that if I compare two objects and their lengths are equal, that my quicksort will sort the object with the smaller source vertex in front of the one with the larger source vertex. If those are also equal, I want to compare the destination vertexes. I want to sort the larger destination vertex in front of that with the smaller source vertex. This will all be done in an array. Below is my implementation of quicksort. Note that e[i] is my object which holds my vertexes and length. 

void quickSort(edge *e, int left, int right)
{
  int i = left, j = right;
  int temp, temp1, temp2;
  while(i <= j)
  {
    while(e[i].getLength() < pivot)
      i++;
    while(e[j].getLength() > pivot)
      j--;
    if(i <= j)
    {
      temp = e[i].getLength();
      temp1 = e[i].getEdgeSrc();
      temp2 = e[i].getEdgeDes();
      e[i].setLength(e[j].getLength());
      e[i].setEdgeSrc(e[j].getEdgeSrc());
      e[i].setEdgeDes(e[j].getEdgeDes());
      e[j].setLength(temp);
      e[j].setEdgeSrc(temp1);
      e[j].setEdgeDes(temp2);
      i++;
      j--;
    } //if statement
  }///while loop
  if(left < j)
    quickSort(e, left, j);
  if(i < right)
    quickSort(e, i, right);

}

Might anyone know how / where to perform the sorting of the vertexes if the lengths are equal? Thanks!

Upvotes: 1

Views: 307

Answers (2)

Jim Mischel
Jim Mischel

Reputation: 134005

You need to create a comparison function and call it rather than comparing the lengths. You don't define pivot anywhere in your code, but I assume it's the same type as is returned by getLength(). You will need to change pivot so that it's an index. Then, you write:

while (compareEdge(e[i], e[pivot]) < 0)
    i++;
while (compareEdge(e[j], e[pivot]) > 0)
    j--;

Your compareEdge function would compare the lengths. If those are equal then it compares the vertices as you described.

Upvotes: 0

jogojapan
jogojapan

Reputation: 69977

Best define a comparison operator for the edge objects that does what you need it to do:

class edge
{
  /* ... */
public:

  bool operator<(const edge &other) const
  {
     /* Length is first criterion: */
     if (length < other.length)
        return true;
     /* Source vertex is second criterion: */
     else if ((length == other.length) && (src < other.src))
        return true;
     return false;
  }

  /* ... */
};

And then, inside your quick sort implementation, you use this operator to compare edge objects, rather than accessing getLength() etc. directly:

while(e[i].getLength() < pivot)
  i++;

becomes

while(e[i] < pivot)
  i++;

And

while(e[j].getLength() > pivot)
  j--;

becomes

while(pivot < e[j])
  j--;

Note that I've only defined operator<, not operator>, so I suggest using only that. Alternatively, you can define operator> as well.

Note that above I assume that pivot is a reference to the current pivot element. If it's actually an integer index to the current pivot, you'll need to replace it with e[pivot].

Separate note: You might want to use std::swap(e[i],e[j]); instead of the long (and error-prone) sequence of get- and set-statements and the temporary variables.

Upvotes: 2

Related Questions