ZetCode

C# Quickselect

last modified November 15, 2026

In this article we implement the quickselect algorithm in C#. Quickselect finds the k-th smallest element of an array without sorting it. We use it to compute medians and to find the k smallest or largest elements, and we compare it with sorting, LINQ and PriorityQueue.

Quickselect algorithm

Quickselect, also known as Hoare's selection algorithm, finds the element that would be at index k if the array were sorted. Like quicksort, it partitions the array around a pivot. After partitioning, the pivot is at its final sorted position p. If p equals k, we are done. Otherwise, quickselect continues only in the part that contains index k; the other part is ignored.

PropertyValue
Average caseO(n)
Worst caseO(n2)
Extra memoryO(1), works in place
Modifies the inputyes

Quicksort recurses into both parts, which gives O(n log n). Quickselect continues into one part, which is about half of the previous one on average, so the total work is n + n/2 + n/4 + ..., which is less than 2n. Random pivots make the quadratic worst case extremely unlikely.

C# quickselect example

The first example finds the smallest elements and the median of an array.

Program.cs
int[] nums = [38, 27, 43, 3, 9, 82, 10, 61, 5, 77, 19];

for (int k = 0; k < 4; k++)
{
    Console.WriteLine($"k={k}: {QuickSelect([.. nums], k)}");
}

Console.WriteLine($"median: {QuickSelect([.. nums], nums.Length / 2)}");
Console.WriteLine($"sorted: {string.Join(" ", nums.Order())}");

static int QuickSelect(int[] arr, int k)
{
    int lo = 0;
    int hi = arr.Length - 1;

    while (lo < hi)
    {
        int p = Partition(arr, lo, hi);

        if (p == k) return arr[p];

        if (k < p)
        {
            hi = p - 1;
        }
        else
        {
            lo = p + 1;
        }
    }

    return arr[lo];
}

static int Partition(int[] arr, int lo, int hi)
{
    int r = Random.Shared.Next(lo, hi + 1);
    (arr[r], arr[hi]) = (arr[hi], arr[r]);

    int pivot = arr[hi];
    int i = lo;

    for (int j = lo; j < hi; j++)
    {
        if (arr[j] < pivot)
        {
            (arr[i], arr[j]) = (arr[j], arr[i]);
            i++;
        }
    }

    (arr[i], arr[hi]) = (arr[hi], arr[i]);
    return i;
}

The QuickSelect method takes the array and a zero-based index k.

Console.WriteLine($"k={k}: {QuickSelect([.. nums], k)}");

Quickselect rearranges the array, so each call gets a copy.

int p = Partition(arr, lo, hi);

if (p == k) return arr[p];

if (k < p)
{
    hi = p - 1;
}
else
{
    lo = p + 1;
}

After the partition, the pivot is at index p, all smaller elements are to its left and all others to its right. The search interval shrinks to the side with index k. A loop replaces the recursion, because there is only one recursive call.

int r = Random.Shared.Next(lo, hi + 1);
(arr[r], arr[hi]) = (arr[hi], arr[r]);

A random element is swapped to the end and used as the pivot. This is Lomuto's partition scheme.

Console.WriteLine($"median: {QuickSelect([.. nums], nums.Length / 2)}");

For an odd number of elements, the median is the element at index n / 2 of the sorted array.

$ dotnet run
k=0: 3
k=1: 5
k=2: 9
k=3: 10
median: 27
sorted: 3 5 9 10 19 27 38 43 61 77 82

Quickselect step by step

The next example prints the search interval after each partition. To get repeatable output, it uses the last element as the pivot.

Program.cs
int[] nums = [38, 27, 43, 3, 9, 82, 10, 61, 5, 77, 19, 50, 2, 94, 33];
int k = 10;

Console.WriteLine($"looking for k={k}");
int res = QuickSelect(nums, k);
Console.WriteLine($"result: {res}");
Console.WriteLine($"array:  {string.Join(" ", nums)}");

static int QuickSelect(int[] arr, int k)
{
    int lo = 0;
    int hi = arr.Length - 1;

    while (lo < hi)
    {
        int p = Partition(arr, lo, hi);
        Console.WriteLine($"[{lo}..{hi}] pivot {arr[p],2} lands at {p,2}: {string.Join(" ", arr[lo..(hi + 1)])}");

        if (p == k) return arr[p];

        if (k < p) hi = p - 1;
        else lo = p + 1;
    }

    return arr[lo];
}

static int Partition(int[] arr, int lo, int hi)
{
    int pivot = arr[hi];
    int i = lo;

    for (int j = lo; j < hi; j++)
    {
        if (arr[j] < pivot)
        {
            (arr[i], arr[j]) = (arr[j], arr[i]);
            i++;
        }
    }

    (arr[i], arr[hi]) = (arr[hi], arr[i]);
    return i;
}

We look for the element at index 10.

The first pivot, 33, lands at index 7, so the element at index 10 is in the right part, and the left part is never touched again. After four partitions, the interval shrinks to the single element at index 10. The array is not sorted, but every element left of index 10 is smaller than 50 and every element right of it is larger.

$ dotnet run
looking for k=10
[0..14] pivot 33 lands at  7: 27 3 9 10 5 19 2 33 43 77 82 50 38 94 61
[8..14] pivot 61 lands at 11: 43 50 38 61 82 94 77
[8..10] pivot 38 lands at  8: 38 50 43
[9..10] pivot 43 lands at  9: 43 50
result: 50
array:  27 3 9 10 5 19 2 33 38 43 50 61 82 94 77

Median and a custom comparer

The generic version takes an IComparer<T>, so we can select objects by any property.

Program.cs
double[] temps = [21.5, 19.0, 24.2, 18.4, 22.8, 20.1, 25.6, 17.9];
Console.WriteLine($"median temperature: {Median(temps)}");

Employee[] emps =
[
    new("Paul", 3200), new("Lucy", 4100), new("Robert", 2900), new("Anna", 5300),
    new("Tom", 3800), new("Jane", 4500), new("Mark", 3100),
];

var bySalary = Comparer<Employee>.Create((a, b) => a.Salary.CompareTo(b.Salary));
Employee mid = QuickSelect(emps, emps.Length / 2, bySalary);
Console.WriteLine($"median salary: {mid}");

static double Median(double[] data)
{
    double[] arr = [.. data];
    int n = arr.Length;
    double upper = QuickSelect(arr, n / 2, Comparer<double>.Default);

    if (n % 2 == 1) return upper;

    double lower = arr[..(n / 2)].Max();
    return (lower + upper) / 2;
}

static T QuickSelect<T>(T[] arr, int k, IComparer<T> cmp)
{
    int lo = 0;
    int hi = arr.Length - 1;

    while (lo < hi)
    {
        int r = Random.Shared.Next(lo, hi + 1);
        (arr[r], arr[hi]) = (arr[hi], arr[r]);

        T pivot = arr[hi];
        int p = lo;

        for (int j = lo; j < hi; j++)
        {
            if (cmp.Compare(arr[j], pivot) < 0)
            {
                (arr[p], arr[j]) = (arr[j], arr[p]);
                p++;
            }
        }

        (arr[p], arr[hi]) = (arr[hi], arr[p]);

        if (p == k) return arr[p];

        if (k < p) hi = p - 1;
        else lo = p + 1;
    }

    return arr[lo];
}

record Employee(string Name, int Salary);

We compute the median of temperatures and the employee with the median salary.

double upper = QuickSelect(arr, n / 2, Comparer<double>.Default);

if (n % 2 == 1) return upper;

double lower = arr[..(n / 2)].Max();

For an even number of elements, the median is the average of the two middle elements. After the selection of the upper middle element, all elements to its left are smaller or equal, so the lower middle element is their maximum. This needs no second selection.

var bySalary = Comparer<Employee>.Create((a, b) => a.Salary.CompareTo(b.Salary));
Employee mid = QuickSelect(emps, emps.Length / 2, bySalary);

The comparer selects employees by salary.

$ dotnet run
median temperature: 20.8
median salary: Employee { Name = Tom, Salary = 3800 }

The k largest elements

After quickselect finds the element at index k - 1, the first k elements of the array are the k smallest ones. With a reversed comparer, they are the k largest.

Program.cs
var rnd = new Random(5);
int[] scores = [.. Enumerable.Range(0, 30).Select(_ => rnd.Next(100))];
Console.WriteLine($"scores: {string.Join(" ", scores)}");

int k = 5;
var desc = Comparer<int>.Create((a, b) => b.CompareTo(a));

int[] arr = [.. scores];
QuickSelect(arr, k - 1, desc);
Console.WriteLine($"top {k} (unordered): {string.Join(" ", arr[..k])}");

Array.Sort(arr, 0, k, desc);
Console.WriteLine($"top {k} (sorted):    {string.Join(" ", arr[..k])}");

var pq = new PriorityQueue<int, int>();

foreach (int s in scores)
{
    pq.Enqueue(s, s);
    if (pq.Count > k) pq.Dequeue();
}

Console.WriteLine($"PriorityQueue:     {string.Join(" ", pq.UnorderedItems.Select(e => e.Element).OrderDescending())}");
Console.WriteLine($"LINQ:              {string.Join(" ", scores.OrderDescending().Take(k))}");

static T QuickSelect<T>(T[] arr, int k, IComparer<T> cmp)
{
    int lo = 0;
    int hi = arr.Length - 1;

    while (lo < hi)
    {
        int r = Random.Shared.Next(lo, hi + 1);
        (arr[r], arr[hi]) = (arr[hi], arr[r]);

        T pivot = arr[hi];
        int p = lo;

        for (int j = lo; j < hi; j++)
        {
            if (cmp.Compare(arr[j], pivot) < 0)
            {
                (arr[p], arr[j]) = (arr[j], arr[p]);
                p++;
            }
        }

        (arr[p], arr[hi]) = (arr[hi], arr[p]);

        if (p == k) return arr[p];

        if (k < p) hi = p - 1;
        else lo = p + 1;
    }

    return arr[lo];
}

We find the five highest of thirty scores with quickselect, a PriorityQueue and LINQ.

QuickSelect(arr, k - 1, desc);

The return value is ignored; we want the side effect. The top five scores are in the first five positions in no particular order. Because of the random pivots, their order may differ from run to run.

Array.Sort(arr, 0, k, desc);

If we need them ordered, we sort only the first k elements.

pq.Enqueue(s, s);
if (pq.Count > k) pq.Dequeue();

A priority queue keeps the k largest elements seen so far and drops the smallest one when it grows larger. It reads the data once and does not modify it, so it works for streams.

$ dotnet run
scores: 33 28 26 62 46 92 14 95 59 11 97 37 6 7 48 15 96 9 81 25 48 7 83 77 18 74 23 78 92 10
top 5 (unordered): 96 95 97 92 92
top 5 (sorted):    97 96 95 92 92
PriorityQueue:     97 96 95 92 92
LINQ:              97 96 95 92 92

Performance

In the last example, we compute the median of ten million random integers and find the hundred smallest of them.

benchmark.cs
#:property PublishAot=false

using System.Diagnostics;

var rnd = new Random(17);
int[] data = [.. Enumerable.Range(0, 10_000_000).Select(_ => rnd.Next())];
int mid = data.Length / 2;

Measure("median, Array.Sort", () => { int[] a = [.. data]; Array.Sort(a); return a[mid]; });
Measure("median, QuickSelect", () => QuickSelect([.. data], mid));
Measure("median, LINQ ElementAt", () => data.Order().ElementAt(mid));

Measure("100 smallest, QuickSelect", () => { int[] a = [.. data]; QuickSelect(a, 99); return a[..100].Max(); });
Measure("100 smallest, PriorityQueue", () => TopK(data, 100));
Measure("100 smallest, LINQ Take", () => data.Order().Take(100).Last());

void Measure(string name, Func<int> f)
{
    f();
    var sw = Stopwatch.StartNew();
    int res = f();
    Console.WriteLine($"{name,-28} {sw.ElapsedMilliseconds,5} ms  {res}");
}

static int TopK(int[] data, int k)
{
    var pq = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));

    foreach (int x in data)
    {
        if (pq.Count < k) pq.Enqueue(x, x);
        else if (x < pq.Peek()) pq.DequeueEnqueue(x, x);
    }

    return pq.Peek();
}

static int QuickSelect(int[] arr, int k)
{
    int lo = 0, hi = arr.Length - 1;

    while (lo < hi)
    {
        int r = Random.Shared.Next(lo, hi + 1);
        (arr[r], arr[hi]) = (arr[hi], arr[r]);

        int pivot = arr[hi];
        int p = lo;

        for (int j = lo; j < hi; j++)
        {
            if (arr[j] < pivot)
            {
                (arr[p], arr[j]) = (arr[j], arr[p]);
                p++;
            }
        }

        (arr[p], arr[hi]) = (arr[hi], arr[p]);

        if (p == k) return arr[p];

        if (k < p) hi = p - 1;
        else lo = p + 1;
    }

    return arr[lo];
}

Each measurement runs once to warm up and once to be timed. The times include copying the 40 MB array where the method modifies its input.

Measure("median, LINQ ElementAt", () => data.Order().ElementAt(mid));

LINQ does not sort the whole sequence when ElementAt follows Order; it uses a quickselect internally. Likewise, Order().Take(100) sorts only the needed part.

if (pq.Count < k) pq.Enqueue(x, x);
else if (x < pq.Peek()) pq.DequeueEnqueue(x, x);

The priority queue is a max-heap of the hundred smallest values. On random data, almost every element is larger than the heap's maximum and is rejected with a single comparison.

Quickselect finds the median about seven times faster than a full sort. For a small k, the priority queue wins easily: O(n log k) with a tiny k beats the O(n) partitioning, which moves elements around. Quickselect times vary between runs because of the random pivots.

$ dotnet run -c Release benchmark.cs
median, Array.Sort             729 ms  1072950669
median, QuickSelect            109 ms  1072950669
median, LINQ ElementAt         313 ms  1072950669
100 smallest, QuickSelect       66 ms  20677
100 smallest, PriorityQueue      8 ms  20677
100 smallest, LINQ Take        104 ms  20677

Source

PriorityQueue<TElement, TPriority> class
Enumerable.ElementAt method

In this article we have implemented the quickselect algorithm in C#.

Other sorting articles in C#:

Author

I am Jan Bodnar, a programmer and technical writer. I have been writing programming tutorials at ZetCode since 2007 and have published eight e-books. See about the author.

List all C# tutorials.