Search code examples
c#quicksortfractions

Sorting fractions with quick sort and specifying between 1/2 and 2/4


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.


Solution

  • 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
    }