How to pass by reference in C#

Question

I am writing a Quick sorting class mimicking the code given in "Algorithms 4" by Sedgewick. The original code is written in Java. I translated in C# the core part but it doesn't seem to work. It seems like the problem is in the line a = a.OrderBy(x => r.Next()).ToArray() but I don't know how to correct it.

I tried to add ref in the Sorts and Partition method signatures but once I call the function Sort(ref a) in Main, the compliler complaints that cannot converte ref System.String[] to ref System.IComparable[]. I also tried to make the first Sort return an IComparable[], the sorted array. However, when I call it in the Main like this string[] nums = (string[]) Sort(nums), it throws a runtime error says Unable to cast object of type 'System.IComparable[]' to type 'System.String[]'.

public class Quick
{
    public static void Sort(IComparable[] a)
    {
        Random r = new Random();
        a = a.OrderBy(x => r.Next()).ToArray();
        Sort(a, 0, a.Length - 1);
    }

    private static void Sort(IComparable[] a, int lo, int hi)
    {
        if (lo >= hi) return;
        int p = Partition(a, lo, hi);
        Sort(a, lo, p - 1);
        Sort(a, p + 1, hi);
    }

    private static int Partition(IComparable[] a, int lo, int hi)
    {
        int i = lo, j = hi;
        IComparable p = a[lo];
        while (true)
        {
            while (Less(a[++i], p))
            {
                if (i == hi)
                    break;
            }

            while (Less(p, a[--j]))
            {
                if (j == lo)
                    break;
            }

            if (i >= j) break;

            Exch(a, i, j);
        }
        Exch(a, lo, j);
        return j;
    }

    private static void Exch(IComparable[] a, int lo, int hi)
    {
        IComparable tmp = a[lo];
        a[lo] = a[hi];
        a[hi] = tmp;
    }

    private static bool Less(IComparable a, IComparable b)
    {
        return a.CompareTo(b) < 0;
    }


    public static void Main(string[] args)
    {
        string[] nums = File.ReadAllLines(args[0]);
        for (int i = 0; i < nums.Length; i++)
        {
            Console.WriteLine(nums[i]);
        }
        Sort(nums);
        Console.WriteLine("After sorting:");
        for (int i = 0; i < nums.Length; i++)
        {
            Console.WriteLine(nums[i]);
        }
        Console.ReadKey();
    }
}

The seconde WriteLine should print out the sorted array but it doesn't.

Answer 1

The problem here is not pass by reference, it is this line, as you have identified:

a = a.OrderBy(x => r.Next()).ToArray();

You are giving a a new value, which is different from just modifying the contents of a. Since the Sort method sorts the array in place, you should not create a new array, and the array doesn’t have to be shuffled before you sort it.

So deleting these two lines should make your code work:

Random r = new Random();
a = a.OrderBy(x => r.Next()).ToArray();

You seem to encounter some problems when you try to return the array from Sort. You can fix this by making all your methods generic, with a generic parameter T constrained to IComparable<T>:

public static T[] Sort<T>(T[] a) where T: IComparable<T>
{
    Random r = new Random();
    a = a.OrderBy(x => r.Next()).ToArray();
    Sort(a, 0, a.Length - 1);
    return a;
}

private static void Sort<T>(T[] a, int lo, int hi) where T: IComparable<T>
{
    if (lo >= hi) return;
    int p = Partition(a, lo, hi);
    Sort(a, lo, p - 1);
    Sort(a, p + 1, hi);
}

private static int Partition<T>(T[] a, int lo, int hi) where T: IComparable<T>
{
    int i = lo, j = hi;
    T p = a[lo];
    while (true)
    {
        while (Less(a[++i], p))
        {
            if (i == hi)
                break;
        }

        while (Less(p, a[--j]))
        {
            if (j == lo)
                break;
        }

        if (i >= j) break;

        Exch(a, i, j);
    }
    Exch(a, lo, j);
    return j;
}

private static void Exch<T>(T[] a, int lo, int hi)
{
    T tmp = a[lo];
    a[lo] = a[hi];
    a[hi] = tmp;
}

private static bool Less<T>(T a, T b) where T: IComparable<T>
{
    return a.CompareTo(b) < 0;
}