I am trying to set up quick sort, and I want it to sort an array of fractions.
Currently, it won't properly sort fractions that have an equal value (e.g. 1/2 and 2/4)
1/2 would need to be before 2/4, yet it ends up completly random.
The code I'm using is this:
public static void quicksort(Fraction[] f, int p, int r)
{
if (p < r)
{
int q = partition(f, p, r);
quicksort(f, p, q - 1);
quicksort(f, q + 1, r);
}
}
public static int partition(Fraction[] f, int p, int r)
{
Fraction pivot = f[r];
int i = p - 1;
for (int j = p; j < r; j++)
{
if (f[j].Value < pivot.Value)
{
i++;
Fraction wissel = f[i];
f[i] = f[j];
f[j] = wissel;
}
else
if (f[j].Value < pivot.Value && f[j].Teller < pivot.Teller)
{
i++;
Fraction wissel = f[i];
f[i] = f[j];
f[j] = wissel;
}
}
Fraction wisselt = f[i + 1];
f[i + 1] = f[r];
f[r] = wisselt;
return i + 1;
}
Can anyone shed some light on how to do this?
EDIT: David Archer's suggestion fixed it, thank you guys.
I'm not sure what Fraction class you are using but if you need to distinguish between 1/2 and 2/4 (which are equal in strict mathematical terms), I'd suggest creating your own comparison methods and using those instead of the built-in greater-than and less-than operators.
bool IsLessThan(Fraction a, Fraction b)
{
// Your code here that results in 1/2 being less than 2/4
}
bool IsGreaterThan(Fraction a, Fraction b)
{
// Your code here that results in 2/4 being greater than 1/2
}