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.
| Property | Value |
|---|---|
| Average case | O(n) |
| Worst case | O(n2) |
| Extra memory | O(1), works in place |
| Modifies the input | yes |
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.
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.
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.
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.
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.
#: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#:
- Bubble sort
- Selection sort
- Insertion sort
- Shell sort
- Merge sort
- Quick sort
- Heap sort
- Counting sort
- Radix sort
- Bucket sort
- Array.Sort and Span.Sort
- Stable sorting
- Binary search
- Introsort
- External sort
- Timsort
Author
List all C# tutorials.