Created
March 20, 2019 04:38
-
-
Save CallumWatkins/116448c01719903b5c109889674e67c4 to your computer and use it in GitHub Desktop.
An in-place quicksort implementation based on the Hoare partition scheme. Designed for Span<T>. License: MIT
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/// <summary> | |
/// An in-place quicksort implementation based on the Hoare partition scheme. | |
/// </summary> | |
/// <typeparam name="T">The type of the elements being sorted.</typeparam> | |
/// <param name="input">A span of elements to be sorted.</param> | |
public static void Quicksort<T>(Span<T> input) where T : IComparable<T> | |
{ | |
Quicksort<T>(input, Comparer<T>.Default); | |
} | |
/// <summary> | |
/// An in-place quicksort implementation based on the Hoare partition scheme. | |
/// </summary> | |
/// <typeparam name="T">The type of the elements being sorted.</typeparam> | |
/// <param name="input">A span of elements to be sorted.</param> | |
/// <param name="comparer">The comparer to use when comparing the elements.</param> | |
public static void Quicksort<T>(Span<T> input, IComparer<T> comparer) | |
{ | |
if (input.Length <= 1) { return; } // Base case | |
T pivot = input[(input.Length - 1) / 2]; | |
int i = -1; | |
int j = input.Length; | |
while (true) | |
{ | |
while (comparer.Compare(input[++i], pivot) < 0) ; | |
while (comparer.Compare(input[--j], pivot) > 0) ; | |
if (i >= j) | |
{ | |
Quicksort(input.Slice(0, j + 1), comparer); | |
if (j + 1 < input.Length) Quicksort(input.Slice(j + 1), comparer); | |
return; | |
} | |
T temp = input[i]; | |
input[i] = input[j]; | |
input[j] = temp; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment