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

Ответ 1

От MSDN:

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

Сорт использует интроспективный вид. (Quicksort в версии 4.0 и более ранней версии .NET framework).

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

Ответ 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);
    }
}

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

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

Ответ 3

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

Ответ 4

Нет, не:

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

Ответ 5

UPDATE: Этот код не стабилизирует 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());