Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is the sorting algorithm used by .NET's `Array.Sort()` method a stable algorithm?

Tags:

c#

.net

Is the sorting algorithm used by .NET's Array.Sort() method a stable algorithm?

like image 269
Pop Catalin Avatar asked Sep 29 '08 09:09

Pop Catalin


People also ask

Which sorting algorithm is stable?

Several common sorting algorithms are stable by nature, such as Merge Sort, Timsort, Counting Sort, Insertion Sort, and Bubble Sort. Others such as Quicksort, Heapsort and Selection Sort are unstable.

Which is not a stable sorting algorithm?

These sorting algorithms are usually not stable: quicksort. heapsort. selection sort.

What is stable or unstable algorithm?

A sorting algorithm is said to be stable if it maintains the relative order of numbers/records in the case of tie i.e. if you need to sort 1 1 2 3 then if you don't change the order of those first two ones then your algorithm is stable, but if you swap them then it becomes unstable, despite the overall result or ...

Why is heapsort not stable?

Heap sort is not stable because operations in the heap can change the relative order of equivalent keys. The binary heap can be represented using array-based methods to reduce space and memory usage. Heap sort is an in-place algorithm, where inputs are overwritten using no extra data structures at runtime.


2 Answers

From MSDN:

This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

The sort uses introspective sort. (Quicksort in version 4.0 and earlier of the .NET framework).

If you need a stable sort, you can use Enumerable.OrderBy.

like image 127
Rasmus Faber Avatar answered Sep 28 '22 04:09

Rasmus Faber


Adding to Rasmus Faber's answer…

Sorting in LINQ, via Enumerable.OrderBy and Enumerable.ThenBy, is a stable sort implementation, which can be used as an alternative to Array.Sort. From Enumerable.OrderBy documentation over at MSDN:

This method performs a stable sort; that is, if the keys of two elements are equal, the order of the elements is preserved. In contrast, an unstable sort does not preserve the order of elements that have the same key.

Also, any unstable sort implementation, like that of Array.Sort, can be stabilized by using the position of the elements in the source sequence or array as an additional key to serve as a tie-breaker. Below is one such implementation, as a generic extension method on any single-dimensional array and which turns Array.Sort into a stable sort:

using System; using System.Collections.Generic;  public static class ArrayExtensions {      public static void StableSort<T>(this T[] values, Comparison<T> comparison) {         var keys = new KeyValuePair<int, T>[values.Length];         for (var i = 0; i < values.Length; i++)             keys[i] = new KeyValuePair<int, T>(i, values[i]);         Array.Sort(keys, values, new StabilizingComparer<T>(comparison));     }      private sealed class StabilizingComparer<T> : IComparer<KeyValuePair<int, T>>      {         private readonly Comparison<T> _comparison;          public StabilizingComparer(Comparison<T> comparison) {             _comparison = comparison;         }          public int Compare(KeyValuePair<int, T> x,                             KeyValuePair<int, T> y) {             var result = _comparison(x.Value, y.Value);             return result != 0 ? result : x.Key.CompareTo(y.Key);         }     } } 

Below is a sample program using StableSort from above:

static class Program  {     static void Main()      {         var unsorted = new[] {             new Person { BirthYear = 1948, Name = "Cat Stevens" },             new Person { BirthYear = 1955, Name = "Kevin Costner" },             new Person { BirthYear = 1952, Name = "Vladimir Putin" },             new Person { BirthYear = 1955, Name = "Bill Gates" },             new Person { BirthYear = 1948, Name = "Kathy Bates" },             new Person { BirthYear = 1956, Name = "David Copperfield" },             new Person { BirthYear = 1948, Name = "Jean Reno" },         };          Array.ForEach(unsorted, Console.WriteLine);          Console.WriteLine();         var unstable = (Person[]) unsorted.Clone();         Array.Sort(unstable, (x, y) => x.BirthYear.CompareTo(y.BirthYear));         Array.ForEach(unstable, Console.WriteLine);          Console.WriteLine();         var stable = (Person[]) unsorted.Clone();         stable.StableSort((x, y) => x.BirthYear.CompareTo(y.BirthYear));         Array.ForEach(stable, Console.WriteLine);     } }  sealed class Person  {     public int BirthYear { get; set; }     public string Name { get; set; }      public override string ToString() {         return string.Format(             "{{ BirthYear = {0}, Name = {1} }}",              BirthYear, Name);     } } 

Below is the output from the sample program above (running on a machine with Windows Vista SP1 and .NET Framework 3.5 SP1 installed):

{ BirthYear = 1948, Name = Cat Stevens } { BirthYear = 1955, Name = Kevin Costner } { BirthYear = 1952, Name = Vladimir Putin } { BirthYear = 1955, Name = Bill Gates } { BirthYear = 1948, Name = Kathy Bates } { BirthYear = 1956, Name = David Copperfield } { BirthYear = 1948, Name = Jean Reno }  { BirthYear = 1948, Name = Jean Reno } { BirthYear = 1948, Name = Kathy Bates } { BirthYear = 1948, Name = Cat Stevens } { BirthYear = 1952, Name = Vladimir Putin } { BirthYear = 1955, Name = Bill Gates } { BirthYear = 1955, Name = Kevin Costner } { BirthYear = 1956, Name = David Copperfield }  { BirthYear = 1948, Name = Cat Stevens } { BirthYear = 1948, Name = Kathy Bates } { BirthYear = 1948, Name = Jean Reno } { BirthYear = 1952, Name = Vladimir Putin } { BirthYear = 1955, Name = Kevin Costner } { BirthYear = 1955, Name = Bill Gates } { BirthYear = 1956, Name = David Copperfield } 
like image 44
Atif Aziz Avatar answered Sep 28 '22 03:09

Atif Aziz