c# - metodos - ordenamiento por intercambio

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

Question

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

Answer 1

Como otras respuestas han declarado, Array.Sort no es estable. Sin embargo, los métodos LINQ OrderBy (y OrderByDescending, etc.) son estables, lo que puede ser muy útil.

Answer 2

No, no es :

Este método usa el algoritmo QuickSort. Esta implementación realiza un tipo inestable

Answer 3

ACTUALIZACIÓN: Este código no estabiliza Array.Sort (asegúrese de que los elementos siempre estén ordenados 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;
        };
    }
}

Utilizar:

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

Answer 4

Desde MSDN :

Esta implementación realiza una clasificación 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 usa tipo introspectivo. (Quicksort en la versión 4.0 y anterior del framework .NET).

Si necesita una clasificación estable, puede usar Enumerable.OrderBy .

Answer 5

Añadiendo a la respuesta de Rasmus Faber ...

La ordenación de LINQ, a través de Enumerable.OrderBy y Enumerable.ThenBy , es una implementación de clasificación estable, que se puede usar como alternativa a Array.Sort . De la documentación de Enumerable.OrderBy en 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.

Además, cualquier implementación de ordenación inestable, como la de Array.Sort , se puede estabilizar utilizando la posición de los elementos en la secuencia fuente o matriz como una clave adicional para servir como un desempate. A continuación se muestra una implementación de este tipo, como un método de extensión genérico en cualquier matriz unidimensional y que convierte Array.Sort en una clasificación 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);
        }
    }
}

A continuación se muestra un programa de ejemplo que usa 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 el resultado 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 }