L'algorithme de tri utilisé par la méthode Array.Sort()
de .NET est-il un algorithme stable ?
Réponses
Trop de publicités?À 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.
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 }
Non, ce n'est pas :
Cette méthode utilise l'algorithme QuickSort. Cette implémentation effectue un tri instable
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());