¿El algoritmo de clasificación utilizado por el método `Array.Sort()` de .NET es un algoritmo estable?

Question

¿El algoritmo de clasificación utilizado por el método Array.Sort() de .NET es un algoritmo stable?

Answer 1

De MSDN:

Esta aplicación realiza una especie inestable; es decir, si dos elementos son iguales, es posible que su orden no se conserve. Por el contrario, un género estable conserva el orden de los elementos que son iguales.

El género utiliza una ordenación introspectiva. (Quicksort en la versión 4.0 y anterior del framework .NET).

Si necesita un tipo estable, puede usar Enumerable.OrderBy.

Answer 2

No, isn't:

Este método utiliza el algoritmo QuickSort. Esta implementación realiza una clasificación inestable

Answer 3

Como han indicado otras respuestas, Array.Sort no es estable. Sin embargo, los métodos LINQ OrderBy (y OrderByDescending, etc.) son stable, que pueden ser muy útiles.

Answer 4

Agregando a Rasmus Faber's answer ...

selección LINQ, a través de Enumerable.OrderBy y Enumerable.ThenBy, es una aplicación ordenación estable, que puede ser utilizado como una alternativa a Array.Sort. De Enumerable.OrderBy documentation over at MSDN:

Este método realiza un tipo estable; es decir, si las claves de dos elementos son iguales, se conserva el orden de los elementos . Por el contrario, una ordenación inestable no conserva el orden de los elementos que tienen la misma clave.

También, cualquier aplicación tipo inestable, como la de Array.Sort, se puede estabilizar mediante el uso de la posición de los elementos en la secuencia de origen o matriz como una tecla adicional para servir como un desempate. A continuación es un tal aplicación, como un método de extensión genérico en cualquier matriz unidimensional y que convierte Array.Sort en una especie estable:

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); 
     } 
    } 
} 

continuación es un programa de muestra usando StableSort desde arriba:

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); 
    } 
} 

a continuación se muestra la salida del programa de ejemplo anterior (que se ejecuta en una máquina con Windows Vista SP1 y .NET Framework 3.5 SP1 instalado):

{ 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 } 

Answer 5

ACTUALIZACIÓN: Este código no estabiliza la matriz.Ordenar (asegúrese de que los elementos se ordenan siempre en el mismo orden):

public static class ComparisonExtensions 
{ 
    public static Comparison<T> WithGetHashCode<T>(this Comparison<T> current) 
    { 
     return (x, y) => 
     { 
      var result = current(x, y); 
      if (result == 0) 
       return x.GetHashCode() - y.GetHashCode(); 
      return result; 
     }; 
    } 
} 

Uso:

Comparison<Person> comparison = (x, y) => x.BirthYear.CompareTo(y.BirthYear); 
Array.Sort(unstable, comparison.WithGetHashCode());