Quicksort in C#.

Links: notebook, html, PDF, python, slides, slides(2), GitHub

Quicksort in C#, use in Python.

from jyquickhelper import add_notebook_menu
add_notebook_menu()

Quicksort implementation

The example comes from Quicksort (Python). This implementation is barely used as the cost of an array already sorted is not linear. Python first.

def qsort(li):
    if li == []:
        return []
    else:
        pivot = li[0]
        lesser = qsort([x for x in li[1:] if x < pivot])
        greater = qsort([x for x in li[1:] if x >= pivot])
        return lesser + [pivot] + greater
l = [ 1,2,3,3,1,6,7,3]
qsort(l)
[1, 1, 2, 3, 3, 3, 6, 7]

C# version

%load_ext csharpy
%%CS cs_qsorto -i System -i System.Linq -d System.Core

public static double[] cs_qsort(double[] li)
{
    if (li.Length == 0)
    {
        return null;
    }
    else
    {
        var pivot = li[0];
        var lesser = cs_qsort(li.Skip(1).Where(x => x < pivot).ToArray());
        var greater = cs_qsort(li.Skip(1).Where(x => x >= pivot).ToArray());
        var res = new double[li.Length];

        if (lesser != null && lesser.Length > 0)
            Array.Copy(lesser, 0, res, 0, lesser.Length);
        int nb = lesser == null ? 0 : lesser.Length;
        res[nb] = pivot;
        if (greater != null && greater.Length > 0)
            Array.Copy(greater, 0, res, nb + 1, greater.Length);

        return res;
    }
}

public static double[] cs_qsorto(object[] li)
{
    return cs_qsort(li.Select(c=> (double)c).ToArray());
}
<function csharpy.runtime.compile.create_cs_function.<locals>.<lambda>(*params)>
li = [2, 4, 5, 3, 1]
lifloat = [float(x) for x in li]
list(cs_qsorto(lifloat))
[1.0, 2.0, 3.0, 4.0, 5.0]

Speed comparison

import random
array = [ random.randint(0,100) for l in range(0,10000)]
arrayf = [ float(x) for x in array]
%timeit qsort(array)
60.2 ms ± 1.74 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit cs_qsorto(arrayf)
33.2 ms ± 881 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit list(sorted(array))
2.07 ms ± 28.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

We see the C# implementation if faster than the equivalent Python implementation but still must slower than the sort function (C implementation and a different sorting algorithm).