Skip to content

Instantly share code, notes, and snippets.

@aannenko

aannenko/Quicksort.cs

Last active October 19, 2021 06:43
Show Gist options
  • Save aannenko/48ae0860df06cb78d81156b952c1eabc to your computer and use it in GitHub Desktop.
Save aannenko/48ae0860df06cb78d81156b952c1eabc to your computer and use it in GitHub Desktop.
Download ZIP
Raw
Quicksort.cs
// Introduction to Algorithms, Third Edition - 2009
using System;
using System.Collections.Generic;
Console.WriteLine(string.Join(' ', new[] { 2, 8, 7, 1, 3, 5, 6, 4 }.QuickSort()));
Console.WriteLine(string.Join(' ', new[] { 31, 41, 59, 26, 41, 58 }.QuickSort()));
static class ArrayExtensions
{
public static T[] QuickSort<T>(this T[] array, IComparer<T> comparer = null)
{
QuickSort(array, 0, array.Length - 1, comparer);
return array;
}
private static void QuickSort<T>(Span<T> array, int left, int right, IComparer<T> comparer = null)
{
if (array.Length < 2 || left >= right)
return;
comparer ??= Comparer<T>.Default;
var pivot = Partition(array, left, right, comparer);
QuickSort(array, left, pivot - 1, comparer);
QuickSort(array, pivot + 1, right, comparer);
}
private static int Partition<T>(Span<T> array, int left, int right, IComparer<T> comparer)
{
var key = array[right];
var pivot = left - 1;
for (int i = left; i < right; i++)
if (comparer.Compare(array[i], key) < 0 && ++pivot < i)
(array[i], array[pivot]) = (array[pivot], array[i]);
if (++pivot < right)
(array[right], array[pivot]) = (array[pivot], array[right]);
return pivot;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment