QuickSort Algorithm in C# (Pivot)
This is an interesting and relatively easy sort algorithm which is built around the creative use of recursion and a pivot point.
//A kind of exchange sort.
public class QuickSort
{
public static List<int> Execute(List<int> list)
{
//Return if nothing to sort
if (list.Count <= 1) { return list; }
//Find a random pivot point
var random = new Random();
var pivotIndex = random.Next(list.Count);
//Take out the pivot
var pivot = list[pivotIndex];
list.RemoveAt(pivotIndex);
//Lesser - Greater Lists
var lesser = new List<int>();
var greater = new List<int>();
//Sort around the pivot
foreach (var item in list)
{
if (item <= pivot)
{
lesser.Add(item);
}
else
{
greater.Add(pivot);
}
}
//Concatenate & Recursion.
return Concatenate(Execute(lesser), pivot, Execute(greater));
}
private static List<int> Concatenate(List<int> lesser, int pivot, List<int> greater)
{
var result = new List<int>(lesser);
result.Add(pivot);
result.AddRange(greater);
return result;
}
}
//A kind of exchange sort.
public class QuickSort
{
public static List<int> Execute(List<int> list)
{
//Return if nothing to sort
if (list.Count <= 1) { return list; }
//Find a random pivot point
var random = new Random();
var pivotIndex = random.Next(list.Count);
//Take out the pivot
var pivot = list[pivotIndex];
list.RemoveAt(pivotIndex);
//Lesser - Greater Lists
var lesser = new List<int>();
var greater = new List<int>();
//Sort around the pivot
foreach (var item in list)
{
if (item <= pivot)
{
lesser.Add(item);
}
else
{
greater.Add(pivot);
}
}
//Concatenate & Recursion.
return Concatenate(Execute(lesser), pivot, Execute(greater));
}
private static List<int> Concatenate(List<int> lesser, int pivot, List<int> greater)
{
var result = new List<int>(lesser);
result.Add(pivot);
result.AddRange(greater);
return result;
}
}
Comments
Post a Comment