62 votes

L'algorithme de tri utilisé par la méthode `Array.Sort ()` de .NET est-il un algorithme stable?

L'algorithme de tri utilisé par la méthode Array.Sort() de .NET est-il un algorithme stable ?

69voto

Rasmus Faber Points 24195

À partir de MSDN:

Cette application effectue un tri instable; c'est, si deux éléments sont égaux, leur ordre peut ne pas être préservée. En revanche, un tri stable conserve l'ordre des éléments qui sont égaux.

Le tri utilise introspective de tri. (Quicksort dans la version 4.0 et versions antérieures du .NET framework).

Si vous avez besoin d'un tri stable, vous pouvez utiliser Énumérable.OrderBy.

65voto

Atif Aziz Points 16967

L'ajout de Rasmus Faber réponse...

Tri dans LINQ, via Énumérable.OrderBy et Énumérable.ThenBy, est un tri stable de la mise en œuvre, qui peut être utilisé comme une alternative à la Matrice.De tri. De Énumérable.OrderBy documentation sur MSDN à l'adresse:

Cette méthode effectue un tri stable; c'est, si les clés de deux éléments sont l'égalité, l'ordre des éléments est préservée. En revanche, l'instabilité de l' le tri ne permet pas de conserver l'ordre de les éléments qui ont la même clé.

Aussi, le tri instable mise en œuvre, comme celle de l' Array.Sort, peut être stabilisée à l'aide de la position des éléments dans la séquence source ou d'une matrice, comme une touche supplémentaire à servir comme un tie-breaker. Ci-dessous est un exemple de mise en œuvre, comme une extension générique de la méthode sur un seul tableau multidimensionnel et qui se transforme Array.Sort en un tri stable:

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

Ci-dessous est un exemple de programme utilisant StableSort ci-dessus:

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

Ci-dessous est le résultat de l'exemple de programme ci-dessus (en cours d'exécution sur une machine avec Windows Vista SP1 et .NET Framework 3.5 SP1 est installé):

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

20voto

Jon Skeet Points 692016

Comme d'autres réponses l'ont indiqué, Array.Sort n'est pas stable. Cependant, les méthodes LINQ OrderBy (et OrderByDescending, etc.) sont stables, ce qui peut s'avérer très utile.

3voto

Konrad Rudolph Points 231505

Non, ce n'est pas :

Cette méthode utilise l'algorithme QuickSort. Cette implémentation effectue un tri instable

-3voto

halority Points 1

UPDATE: Ce code ne stabilise pas Array.Sort (assurez-vous que les éléments sont toujours triés dans le même ordre):

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

Utilisation:

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

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X