Является ли алгоритм сортировки, используемый методом.NET Array.Sort()`стабильным алгоритмом?

Question

Является ли алгоритм сортировки.NET Array.Sort() метод стабильного алгоритма?

Answer 1

Из MSDN:

Эта реализация выполняет нестабильную сортировку; то есть, если два элемента равны, их порядок может не сохраниться. Напротив, стабильная сортировка сохраняет порядок элементов, которые равны.

Сортировка использует интроспективную сортировку. (Быстрая сортировка в версии 4.0 и более ранних версиях.NET Framework).

Если вам нужна стабильная сортировка, вы можете использовать Enumerable.OrderBy.

Answer 2

Добавляем к ответу Расмуса Фабера...

Сортировка в LINQ через Enumerable.OrderBy и Enumerable.ThenBy является стабильной реализацией сортировки, которую можно использовать в качестве альтернативы Array.Sort. Из документации Enumerable.OrderBy на MSDN:

Этот метод выполняет стабильную сортировку; то есть, если ключи двух элементов равны, порядок элементов сохраняется. Напротив, нестабильная сортировка не сохраняет порядок элементов, имеющих одинаковый ключ.

Кроме того, любая нестабильная реализация сортировки, такая как Array.Sort, можно стабилизировать, используя положение элементов в исходной последовательности или массиве в качестве дополнительного ключа, который служит в качестве прерывателя связей. Ниже приведена одна из таких реализаций, как универсальный метод расширения для любого одномерного массива, который Array.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);
        }
    }
}

Ниже приведен пример программы с использованием StableSort сверху:

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

Ниже приведен пример вышеприведенного примера программы (работающей на компьютере с установленными Windows Vista SP1 и.NET Framework 3.5 SP1):

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

Как указали другие ответы, Array.Sort не является стабильным. Однако методы LINQ OrderBy (и OrderByDescending и т. Д.) Стабильны, что может быть очень полезно.

Answer 4

Нет, это не так:

Этот метод использует алгоритм быстрой сортировки. Эта реализация выполняет нестабильную сортировку

Answer 5

ОБНОВЛЕНИЕ: Этот код не стабилизирует Array.Sort (убедитесь, что элементы всегда сортируются в одном и том же порядке):

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

Использование:

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