The sort API is implemented using Extension methods technique, same as Search API, which means you can use the following method on any collection that implements IList:
- Sort - allows to select sorting strategy and returns a sorted collection.
This is a full example of using Sort API:
internal class Program
{
private static void Main(string[] args)
{
var collection = new List<int> {2, 5, 3, 1, 4};
var sorted = collection.Sort(o => o.UseBubbleSort<int, IntComparer>());
Console.WriteLine($"Sorted collection: {string.Join(", ", sorted)}");
}
}
public sealed class IntComparer : IComparer<int>
{
public int Compare(int x, int y)
{
return x.CompareTo(y);
}
}All sort algorithms require comparisons, the approach is the same as described in Search API, we have 3 options:
- Provide a custom implementation of IComparer interface for the give type T. Comparer must have a default ctor. Below is the example of such comparer for type int and its usage in Bubble Sort:
// Omited for clarity
var result = collection.Sort(o => o.UseBubbleSort<int, IntComparer>());
// Omited for clarity- Pass an instance of a custom comparer implementation. This may be choosen for multiple reasons, such as not wanting to create a new instance per each call or need to inject services via ctor:
// Omited for clarity
var comparer = new IntComparer();
var result = collection.Sort(o => o.UseBubbleSort<int>(comparer));
// Omited for clarity- Pass in a lambda that performs the comparison. This is probably less useful, but enables us to provide a comparison function inline with the call:
// Omited for clarity
var result = collection.Sort(o => o.UseBubbleSort<int>((x, y) => x.CompareTo(y)));
// Omited for clarityBubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller or larger elements "bubble" to the top of the list.
Can be used as an introduction for studying sort algorithms, due to it's simplicity.
- Best Case: O(n)
- Average Case: O(n * n)
- Worst Case: O(n * n)
- Space: O(1)
- In Place
- Stable
// Omited for clarity
var sorted = collection.Sort(o => o.UseBubbleSort<int, IntComparer>());
// Omited for clarity// Omited for clarity
var comparer = new IntComparer();
var result = collection.Sort(o => o.UseBubbleSort<int>(comparer));
// Omited for clarity
}// Omited for clarity
var result = collection.Sort(o => o.UseBubbleSort<int>((x, y) => x.CompareTo(y)));
// Omited for clarity
}Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as Quick, Heap, or Merge Sort.
Efficient for (quite) small and/or partially sorted data sets. More efficient than Selection Sort or Bubble Sort. Can be used for sorting data as it arrives.
- Best Case: O(n)
- Average Case: O(n * n)
- Worst Case: O(n * n)
- Space: O(1)
- In Place
- Stable
// Omited for clarity
var sorted = collection.Sort(o => o.UseInsertionSort<int, IntComparer>());
// Omited for clarity// Omited for clarity
var comparer = new IntComparer();
var result = collection.Sort(o => o.UseInsertionSort<int>(comparer));
// Omited for clarity
}// Omited for clarity
var result = collection.Sort(o => o.UseInsertionSort<int>((x, y) => x.CompareTo(y)));
// Omited for clarity
}Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (Bubble Sort) or sorting by insertion (Insertion Sort). The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements, it can move some out-of-place elements into position faster than a simple nearest neighbor exchange.
It is a sort of optimized version of Insertion Sort. The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem.
- Best Case: O(n)
- Average Case: O(n * n)
- Worst Case: O(n * n)
- Space: O(1)
- In Place
- Stable
// Omited for clarity
var sorted = collection.Sort(o => o.UseShellSort<int, IntComparer>());
// Omited for clarity// Omited for clarity
var comparer = new IntComparer();
var result = collection.Sort(o => o.UseShellSort<int>(comparer));
// Omited for clarity
}// Omited for clarity
var result = collection.Sort(o => o.UseShellSort<int>((x, y) => x.CompareTo(y)));
// Omited for clarity
}Or alternatively we can provide a custom Increment Factory Method like so:
// Omited for clarity
var sorted = collection.Sort(o => o.UseShellSort<int, IntComparer>(collection => collection.Count / 2);
// Omited for clarity// Omited for clarity
var comparer = new IntComparer();
var result = collection.Sort(o => o.UseShellSort<int>(comparer, collection => collection.Count / 2));
// Omited for clarity
}// Omited for clarity
var result = collection.Sort(o => o.UseShellSort<int>((x, y) => x.CompareTo(y), collection => collection.Count / 2));
// Omited for clarity
}In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar Insertion Sort.
Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.
- Best Case: O(n * n)
- Average Case: O(n * n)
- Worst Case: O(n * n)
- Space: O(1)
- In Place
- Stable
// Omited for clarity
var sorted = collection.Sort(o => o.UseSelectionSort<int, IntComparer>());
// Omited for clarity// Omited for clarity
var comparer = new IntComparer();
var result = collection.Sort(o => o.UseSelectionSort<int>(comparer));
// Omited for clarity
}// Omited for clarity
var result = collection.Sort(o => o.UseSelectionSort<int>((x, y) => x.CompareTo(y)));
// Omited for clarity
}Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of a random access file or an array in order. It is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, Merge Sort and Heap Sort.
Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.
- Best Case: O(n * log(n))
- Average Case: O(n * log(n))
- Worst Case: O(n * log(n))
- Space: O(n)
- Not In Place
- Not Stable
// Omited for clarity
var sorted = collection.Sort(o => o.UseQuickSort<int, IntComparer>());
// Omited for clarity// Omited for clarity
var comparer = new IntComparer();
var result = collection.Sort(o => o.UseQuickSort<int>(comparer));
// Omited for clarity
}// Omited for clarity
var result = collection.Sort(o => o.UseQuickSort<int>((x, y) => x.CompareTo(y)));
// Omited for clarity
}In computer science, merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output. Merge sort is a divide and conquer algorithm.
Although Heap Sort has the same time bounds as merge sort, it requires only Θ(1) auxiliary space instead of merge sort's Θ(n). On typical modern architectures, efficient Quick Sort implementations generally outperform mergesort for sorting RAM-based arrays. On the other hand, merge sort is a stable sort and is more efficient at handling slow-to-access sequential media. Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as Quick Sort) perform poorly, and others (such as Heap Sort) completely impossible.
- Best Case: O(n * log(n))
- Average Case: O(n * log(n))
- Worst Case: O(n * n)
- Space: O(n)
- Not In Place
- Stable
// Omited for clarity
var sorted = collection.Sort(o => o.UseMergeSort<int, IntComparer>());
// Omited for clarity// Omited for clarity
var comparer = new IntComparer();
var result = collection.Sort(o => o.UseMergeSort<int>(comparer));
// Omited for clarity
}// Omited for clarity
var result = collection.Sort(o => o.UseMergeSort<int>((x, y) => x.CompareTo(y)));
// Omited for clarity
}In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved Selection Sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.
Heap sort algorithm has limited uses because Quick Sort and Merge Sort are better in practice. Nevertheless, the Heap data structure itself is enormously used.
- Best Case: O(n * log(n))
- Average Case: O(n * log(n))
- Worst Case: O(n * n)
- Space: O(n)
- In Place
- Not Stable
// Omited for clarity
var sorted = collection.Sort(o => o.UseHeapSort<int, IntComparer>());
// Omited for clarity// Omited for clarity
var comparer = new IntComparer();
var result = collection.Sort(o => o.UseHeapSort<int>(comparer));
// Omited for clarity
}// Omited for clarity
var result = collection.Sort(o => o.UseHeapSort<int>((x, y) => x.CompareTo(y)));
// Omited for clarity
}