Skip to content

Instantly share code, notes, and snippets.

@Swimburger
Last active August 3, 2021 17:51
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Swimburger/7731740ec4c5dafa702144d98bb5c830 to your computer and use it in GitHub Desktop.
Save Swimburger/7731740ec4c5dafa702144d98bb5c830 to your computer and use it in GitHub Desktop.
Generic QuickSort in C#
using System;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
var numbers = new int[] { 5, 4, 5, 7, 6, 9, 4, 1, 1, 3, 4, 50, 56, 41 };
QuickSort(numbers);
PrintList(numbers);
Console.ReadKey();
}
private static void QuickSort<T>(T[] list) where T : IComparable
{
QuickSortInternal(list, 0, list.Length - 1);
}
private static void QuickSortInternal<T>(T[] list, int left, int right) where T : IComparable
{
if(left >= right)
{
return;
}
int partition = PartitionInternal(list, left, right);
QuickSortInternal(list, left, partition - 1);
QuickSortInternal(list, partition + 1, right);
}
private static int PartitionInternal<T>(T[] list, int left, int right) where T : IComparable
{
T partition = list[right];
// stack items smaller than partition from left to right
int swapIndex = left;
for (int i = left; i < right; i++)
{
T item = list[i];
if(item.CompareTo(partition) <= 0)
{
list[i] = list[swapIndex];
list[swapIndex] = item;
swapIndex++;
}
}
// put the partition after all the smaller items
list[right] = list[swapIndex];
list[swapIndex] = partition;
return right;
}
private static void PrintList<T>(IEnumerable<T> list)
{
foreach (var item in list)
{
Console.WriteLine(item);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment