Class SelectionSort

An IInputMutatingSort implementation based on selection sort.

Inheritance
System.Object
SelectionSort
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.Lists.Sorting
Assembly: MoreStructures.dll
Syntax
public class SelectionSort : IInputMutatingSort
Remarks

ADVANTAGES AND DISADVANTAGES
- The algorithm performs sorting in place and is online.
- It is not stable in its basic form and requires additional space or specific assumptions on the type of list being sorted (such as it being a linked list).
- Compared to other quadratic comparison-based algorithms, such as InsertionSort, it is generally simpler but requires in average an higher number of comparisons, therefore yielding worse performance.
- Compared to linearithmic comparison-based algorithms, such as HeapSort, it is way simpler to understand and predict in exact number of operations executed. However, the performance is sensibly worse.
- Compared to non-comparison-based algorithms, such as counting sort, it doesn't require any assumption on the type or values of the items in the input, the only requirement being their total comparability and the comparison behaving according to total order operators rules.

ALGORITHM
- This sorting algorithm split the list L being sorted in two parts: the sorted part, located at the beginning of the list (L[..i]), and the unsorted part, located at the end of the list (L[i..]).
- At the beginning the sorted part is empty (i.e. length 0) and the unsorted part covers the entire list (i.e. length n).
- The algorithm runs n iterations, where n is the number of items in the list.
- At the beginning of iteration i, the sorted sub-list is L[..i] and the unsorted sub-list is L[i..].
- The unsorted sub-list L[i..] is scanned linearly, looking for the index j, between i and n - 1, of the item of L[i..] with minimum value.
- L[i] is swapped with L[j] and the iteration i terminates.
- Now L[..(i + 1)] is the new sorted sub-list, and L[(i + 1)..] is the new unsorted sub-list.

COMPLEXITY
- Each of the n iterations runs n - i - 1 comparisons, to identify the index of the item with the minimum value in the sub-list L[i..].
- The total number of comparisons, over the n iterations, is around n * n / 2.
- Therefore, Time Complexity is O(n^2) and Space Complexity is O(1), since the algorithm runs in place.

Methods

| Improve this Doc View Source

Sort<T>(IList<T>)


Uses the selection sort algorithm with the default comparer for T, given by .

Declaration
public void Sort<T>(IList<T> list)
    where T : IComparable<T>
Parameters
Type Name Description
IList<T> list
Type Parameters
Name Description
T
Remarks

| Improve this Doc View Source

Sort<T>(IList<T>, IComparer<T>)


Uses the selection sort algorithm with the specified comparer.

Declaration
public void Sort<T>(IList<T> list, IComparer<T> comparer)
Parameters
Type Name Description
IList<T> list
IComparer<T> comparer
Type Parameters
Name Description
T
Remarks

Implements

Extension Methods