Menu
Why is the following code
Array.Sort(values);
Array.Reverse(values);
much faster at sorting an array in descending order compared to
Array.Sort(values, (a,b)=>(-a.CompareTo(b)));
Code was run in Release mode outside of the debugger.
What is the most efficient way to produce a descending sort for arrays, preferably in a one liner?
570
If you've observed, the time complexity of Quicksort is O(n logn) in the best and average case scenarios and O(n^2) in the worst case. But since it has the upper hand in the average cases for most inputs, Quicksort is generally considered the “fastest” sorting algorithm.
Among the classical sorting algorithms, heap sort will do well when the input turns out to be (almost) sorted in descending order, as then the max-heap construction phase will involve (almost) no swaps (while the most swaps would occur when the input was already sorted in ascending order).
We can sort arrays in ascending order using the sort() method which can be accessed from the Arrays class. The sort() method takes in the array to be sorted as a parameter. To sort an array in descending order, we used the reverseOrder() method provided by the Collections class.
Quicksort. Quicksort is one of the most efficient sorting algorithms, and this makes of it one of the most used as well. The first thing to do is to select a pivot number, this number will separate the data, on its left are the numbers smaller than it and the greater numbers on the right.
That's a great question. I bet your values array is an array of primitive type!
It's really the sort that is dominant here, because the complexity of Reverse is O(n), while the sort is O(n logn).
The thing is that when sorting primitive types, .NET actually calls a native function, which is extremely fast - much faster that using a Comparison or Comparator.
The function is called TrySZSort:
[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
[SecurityCritical]
[MethodImpl(MethodImplOptions.InternalCall)]
private static bool TrySZSort(Array keys, Array items, int left, int right);
and here is how it's called in the Array class:
[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
[SecuritySafeCritical]
public static void Sort<T>(T[] array, int index, int length, IComparer<T> comparer)
{
if (array == null)
throw new ArgumentNullException("array");
else if (index < 0 || length < 0)
throw new ArgumentOutOfRangeException(length < 0 ? "length" : "index", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
else if (array.Length - index < length)
throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
else if (length > 1 && (comparer != null && comparer != Comparer<T>.Default || !Array.TrySZSort((Array) array, (Array) null, index, index + length - 1)))
ArraySortHelper<T>.Default.Sort(array, index, length, comparer);
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
