# Quicksort in C#.¶

Quicksort in C#, use in Python.

from jyquickhelper import 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).