L’algoritmo di ordinamento utilizzato dal metodo `Array.Sort ()` di .NET è un algoritmo stabile?

L’algoritmo di ordinamento utilizzato dal metodo Array.Sort() di .NET è un algoritmo stabile ?

Da MSDN :

Questa implementazione esegue un ordinamento instabile; cioè, se due elementi sono uguali, il loro ordine potrebbe non essere conservato. Al contrario, un ordinamento stabile conserva l’ordine degli elementi uguali.

L’ordinamento usa un ordinamento introspettivo. (Quicksort nella versione 4.0 e precedenti del framework .NET).

Se hai bisogno di un ordinamento stabile, puoi usare Enumerable.OrderBy .

Aggiunta alla risposta di Rasmus Faber …

L’ordinamento in LINQ, tramite Enumerable.OrderBy e Enumerable.ThenBy , è un’implementazione di ordinamento stabile, che può essere utilizzata in alternativa a Array.Sort . Dalla documentazione Enumerable.OrderBy su MSDN :

Questo metodo esegue un ordinamento stabile; cioè, se le chiavi di due elementi sono uguali, l’ordine degli elementi viene mantenuto. Al contrario, un ordinamento instabile non conserva l’ordine degli elementi che hanno la stessa chiave.

Inoltre, qualsiasi implementazione di ordinamento instabile, come quella di Array.Sort , può essere stabilizzata utilizzando la posizione degli elementi nella sequenza o nell’array sorgente come chiave aggiuntiva da utilizzare come tie-breaker. Di seguito è riportata una implementazione di questo tipo, come metodo di estensione generico su qualsiasi array monodesmensionale e che trasforma Array.Sort in un ordinamento stabile:

 using System; using System.Collections.Generic; public static class ArrayExtensions { public static void StableSort(this T[] values, Comparison comparison) { var keys = new KeyValuePair[values.Length]; for (var i = 0; i < values.Length; i++) keys[i] = new KeyValuePair(i, values[i]); Array.Sort(keys, values, new StabilizingComparer(comparison)); } private sealed class StabilizingComparer : IComparer> { private readonly Comparison _comparison; public StabilizingComparer(Comparison comparison) { _comparison = comparison; } public int Compare(KeyValuePair x, KeyValuePair y) { var result = _comparison(x.Value, y.Value); return result != 0 ? result : x.Key.CompareTo(y.Key); } } } 

Di seguito è riportato un esempio di programma che utilizza StableSort dall’alto:

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

Di seguito è riportato l’output del programma di esempio riportato sopra (in esecuzione su una macchina con Windows Vista SP1 e .NET Framework 3.5 SP1 installati):

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

Come hanno affermato altre risposte, Array.Sort non è stabile. Tuttavia, i metodi LINQ OrderBy (e OrderByDescending ecc.) Sono stabili, il che può essere molto utile.

No, non lo è :

Questo metodo utilizza l’algoritmo QuickSort. Questa implementazione esegue un ordinamento instabile

AGGIORNAMENTO: questo codice non sta stabilizzando Array.Sort (assicurati che gli elementi siano sempre ordinati nello stesso ordine):

 public static class ComparisonExtensions { public static Comparison WithGetHashCode(this Comparison current) { return (x, y) => { var result = current(x, y); if (result == 0) return x.GetHashCode() - y.GetHashCode(); return result; }; } } 

Uso:

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