Class Sort

Namespace

AlgorithmsSW.Sort

Assembly

AlgorithmsSW.dll

Provides a variety of sorting algorithms.

public static class Sort

Inheritance

object

Sort

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Methods

AreElementsEqual<T>(IReadonlyRandomAccessList<T>, IReadonlyRandomAccessList<T>, int, int)

public static bool AreElementsEqual<T>(IReadonlyRandomAccessList<T> array1, IReadonlyRandomAccessList<T> array2, int start, int end) where T : IComparable<T>

Parameters

array1 IReadonlyRandomAccessList<T>

array2 IReadonlyRandomAccessList<T>

start int

end int

Returns

bool

Type Parameters

T

DequeueSortWithDeque<T>(IDeque<T>)

[ExerciseReference(2, 1, 14)]
public static void DequeueSortWithDeque<T>(IDeque<T> deque) where T : IComparable<T>

Parameters

deque IDeque<T>

Type Parameters

T

DequeueSortWithDeque<T>(IRandomAccessList<T>)

[ExerciseReference(2, 1, 14)]
public static void DequeueSortWithDeque<T>(IRandomAccessList<T> list) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

Type Parameters

T

DequeueSortWithQueue<T>(IRandomAccessList<T>)

[ExerciseReference(2, 1, 14)]
public static void DequeueSortWithQueue<T>(IRandomAccessList<T> list) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

Type Parameters

T

DutchFlagSort(IRandomAccessList<int>)

public static void DutchFlagSort(IRandomAccessList<int> list)

Parameters

list IRandomAccessList<int>

DutchFlagSort<T>(IRandomAccessList<T>, T, T, T)

Sorts a list containing only three distinct elements into a given order, in O(n) time complexity. This is based on the Dutch National Flag sorting problem, which is solved here in a single linear pass.

public static void DutchFlagSort<T>(IRandomAccessList<T> list, T smallElement, T mediumElement, T largeElement)

Parameters

list IRandomAccessList<T>

The list to be sorted. It must support random access.

smallElement T

The element considered as the "small" element in the sorting order.

mediumElement T

The element considered as the "medium" element in the sorting order.

largeElement T

The element considered as the "large" element in the sorting order.

Type Parameters

T

The type of elements in the list. Must support equality comparison.

Exceptions

ArgumentNullException

list is null.

ArgumentException

list contains elements other than the specified small, medium, or large elements.

ArgumentException

smallElement equals largeElement but not mediumElement.

GnomeSort<T>(IRandomAccessList<T>)

Performs the Gnome sort algorithm on a list, which is a simple comparison-based sorting algorithm.

public static void GnomeSort<T>(IRandomAccessList<T> list) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

The list to be sorted. It must support random access by index.

Type Parameters

T

The type of elements in the list, which must implement IComparable<T>.

Remarks

The performance of Gnome sort is O(n^2) in the average and worst cases.

Exceptions

ArgumentNullException

Thrown if the list is null.

See Also

https://en.wikipedia.org/wiki/Gnome_sort

HeapSort<T>(IRandomAccessList<T>)

[AlgorithmReference(2, 7)]
public static void HeapSort<T>(IRandomAccessList<T> list) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

Type Parameters

T

InsertionSort<T>(IRandomAccessList<T>, IComparer<T>)

Performs insertion sort algorithm on a list.

[AlgorithmReference(2, 2)]
public static void InsertionSort<T>(IRandomAccessList<T> list, IComparer<T> comparer)

Parameters

list IRandomAccessList<T>

comparer IComparer<T>

Type Parameters

T

InsertionSort<T>(IRandomAccessList<T>, int, int, IComparer<T>)

Performs insertion sort algorithm on a list.

public static void InsertionSort<T>(IRandomAccessList<T> list, int start, int end, IComparer<T> comparer)

Parameters

list IRandomAccessList<T>

start int

end int

comparer IComparer<T>

Type Parameters

T

IsSortedAscending<T>(IReadonlyRandomAccessList<T>)

public static bool IsSortedAscending<T>(IReadonlyRandomAccessList<T> array) where T : IComparable<T>

Parameters

array IReadonlyRandomAccessList<T>

Returns

bool

Type Parameters

T

IsSortedAscending<T>(IReadonlyRandomAccessList<T>, int, int)

public static bool IsSortedAscending<T>(IReadonlyRandomAccessList<T> array, int start, int end) where T : IComparable<T>

Parameters

array IReadonlyRandomAccessList<T>

start int

end int

Returns

bool

Type Parameters

T

IsSortedDescending<T>(IReadonlyRandomAccessList<T>)

public static bool IsSortedDescending<T>(IReadonlyRandomAccessList<T> array) where T : IComparable<T>

Parameters

array IReadonlyRandomAccessList<T>

Returns

bool

Type Parameters

T

IsSortedDescending<T>(IReadonlyRandomAccessList<T>, int, int)

public static bool IsSortedDescending<T>(IReadonlyRandomAccessList<T> array, int start, int end) where T : IComparable<T>

Parameters

array IReadonlyRandomAccessList<T>

start int

end int

Returns

bool

Type Parameters

T

IsSorted<T>(IReadonlyRandomAccessList<T>, IComparer<T>?)

Checks whether a list is sorted.

public static bool IsSorted<T>(IReadonlyRandomAccessList<T> list, IComparer<T>? comparer = null)

Parameters

list IReadonlyRandomAccessList<T>

A list of elements to check. Cannot be null.

comparer IComparer<T>

A comparer to use to compare elements. If not supplied or null, Default is used.

Returns

bool

true the list is sorted, false otherwise.

Type Parameters

T

MedianOf5<T>(T, T, T, T, T)

public static T MedianOf5<T>(T a, T b, T c, T d, T e) where T : IComparable<T>

Parameters

a T

b T

c T

d T

e T

Returns

T

Type Parameters

T

Merge3Sort<T>(IRandomAccessList<T>)

[ExerciseReference(2, 2, 22)]
public static void Merge3Sort<T>(IRandomAccessList<T> list) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

Type Parameters

T

MergeKSortBottomUp<T>(IRandomAccessList<T>, int)

public static void MergeKSortBottomUp<T>(IRandomAccessList<T> list, int k) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

k int

Type Parameters

T

MergeKSort<T>(IRandomAccessList<T>, int)

[ExerciseReference(2, 2, 22)]
public static void MergeKSort<T>(IRandomAccessList<T> list, int k = 3) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

k int

Type Parameters

T

MergeK<T>(IRandomAccessList<T>, T[], int[], int[])

[ExerciseReference(2, 2, 25)]
public static void MergeK<T>(IRandomAccessList<T> list, T[] helpList, int[] startIndices, int[] indexes) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

helpList T[]

startIndices int[]

indexes int[]

Type Parameters

T

MergeSortBottomUp<T>(IRandomAccessList<T>)

public static void MergeSortBottomUp<T>(IRandomAccessList<T> list) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

Type Parameters

T

MergeSortBottomUp<T>(IRandomAccessList<T>, MergeSortConfig)

public static void MergeSortBottomUp<T>(IRandomAccessList<T> list, Sort.MergeSortConfig config) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

config Sort.MergeSortConfig

Type Parameters

T

MergeSortBottomsUpWithQueues<T>(IRandomAccessList<T>, FixedPreInitializedPool<IQueue<IQueue<T>>>, FixedPreInitializedPool<IQueue<T>>)

public static void MergeSortBottomsUpWithQueues<T>(IRandomAccessList<T> list, FixedPreInitializedPool<IQueue<IQueue<T>>> majorQueues, FixedPreInitializedPool<IQueue<T>> minorQueues) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

majorQueues FixedPreInitializedPool<IQueue<IQueue<T>>>

minorQueues FixedPreInitializedPool<IQueue<T>>

Type Parameters

T

MergeSortBottomsUpWithQueues<T>(IRandomAccessList<T>, IFactory<IQueue<IQueue<T>>>?, IFactory<IQueue<T>>?)

[ExerciseReference(2, 2, 15)]
public static void MergeSortBottomsUpWithQueues<T>(IRandomAccessList<T> list, IFactory<IQueue<IQueue<T>>>? majorQueueFactory = null, IFactory<IQueue<T>>? minorQueueFactory = null) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

majorQueueFactory IFactory<IQueue<IQueue<T>>>

minorQueueFactory IFactory<IQueue<T>>

Type Parameters

T

MergeSortNatural<T>(IRandomAccessList<T>)

[ExerciseReference(2, 2, 16)]
public static void MergeSortNatural<T>(IRandomAccessList<T> list) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

Type Parameters

T

MergeSort<T>(IRandomAccessList<T>)

public static void MergeSort<T>(IRandomAccessList<T> list) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

Type Parameters

T

MergeSort<T>(IRandomAccessList<T>, MergeSortConfig)

[AlgorithmReference(2, 4)]
public static void MergeSort<T>(IRandomAccessList<T> list, Sort.MergeSortConfig config) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

config Sort.MergeSortConfig

Type Parameters

T

Merge<T>(IQueue<T>, IQueue<T>, IQueue<T>)

Merge two sorted queues into a result queue.

[ExerciseReference(2, 2, 14)]
public static void Merge<T>(IQueue<T> leftQueue, IQueue<T> rightQueue, IQueue<T> result) where T : IComparable<T>

Parameters

leftQueue IQueue<T>

rightQueue IQueue<T>

result IQueue<T>

Type Parameters

T

MoveNLowestToLeft<T>(IRandomAccessList<T>, int, QuickSortConfig)

public static void MoveNLowestToLeft<T>(IRandomAccessList<T> list, int n, Sort.QuickSortConfig config) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

n int

config Sort.QuickSortConfig

Type Parameters

T

Partition<T>(IRandomAccessList<T>, int, int, QuickSortConfig)

public static int Partition<T>(IRandomAccessList<T> list, int start, int end, Sort.QuickSortConfig config) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

start int

end int

config Sort.QuickSortConfig

Returns

int

Type Parameters

T

QuickSort<T>(IRandomAccessList<T>, QuickSortConfig)

[AlgorithmReference(2, 5)]
public static void QuickSort<T>(IRandomAccessList<T> list, Sort.QuickSortConfig config) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

config Sort.QuickSortConfig

Type Parameters

T

QuickTwoKey<T>(IRandomAccessList<T>)

public static void QuickTwoKey<T>(IRandomAccessList<T> list) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

Type Parameters

T

SelectNthLowest<T>(IRandomAccessList<T>, int, QuickSortConfig)

public static IComparable<T> SelectNthLowest<T>(IRandomAccessList<T> list, int n, Sort.QuickSortConfig config) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

n int

config Sort.QuickSortConfig

Returns

IComparable<T>

Type Parameters

T

SelectionSort<T>(IRandomAccessList<T>)

[AlgorithmReference(2, 1)]
public static void SelectionSort<T>(IRandomAccessList<T> list) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

Type Parameters

T

ShellSortWithPrattSequence<T>(IRandomAccessList<T>)

[AlgorithmReference(2, 3)]
public static void ShellSortWithPrattSequence<T>(IRandomAccessList<T> list) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

Type Parameters

T

ShellSort<T>(IRandomAccessList<T>, int[])

public static void ShellSort<T>(IRandomAccessList<T> list, int[] stepSizes) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

stepSizes int[]

Type Parameters

T

Sort2(IRandomAccessList<int>)

Sorts a list containing only 0 and 1.

public static void Sort2(IRandomAccessList<int> list)

Parameters

list IRandomAccessList<int>

The list to sort.

Sort2<T>(IRandomAccessList<T>, T, T)

Sorts a list containing only two elements in O(n) time.

public static void Sort2<T>(IRandomAccessList<T> list, T smallElement, T largeElement)

Parameters

list IRandomAccessList<T>

The list to sort.

smallElement T

The smaller element.

largeElement T

The larger element.

Type Parameters

T

The type of the elements in the list.

Remarks

The list is sorted so that all instances of smallElement come before instances of largeElement. The order is does not depend on external orderings, for example, if smallElement is given as 1 and largeElement is given as 0, then the list is sorted so that all 1s appear before all 0s. .

SortSmall<T>(IRandomAccessList<T>)

public static void SortSmall<T>(IRandomAccessList<T> list) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

Type Parameters

T

SortStable<T>(IRandomAccessList<T>)

public static void SortStable<T>(IRandomAccessList<T> list) where T : IComparable<T>

Parameters

list IRandomAccessList<T>

Type Parameters

T