Perché List < T > .Sort metodo riordina uguale IComparable < T > elementi?

Question

Ho un problema con il modo in cui il metodo List Sort gestisce l'ordinamento. Dato il seguente elemento:

class Element : IComparable<Element>
{
    public int Priority { get; set; }
    public string Description { get; set; }

    public int CompareTo(Element other)
    {
        return Priority.CompareTo(other.Priority);
    }
}

Se provo a ordinare in questo modo:

List<Element> elements = new List<Element>()
                             {
                                 new Element()
                                     {
                                         Priority = 1,
                                         Description = "First"
                                     },
                                 new Element()
                                     {
                                         Priority = 1,
                                         Description = "Second"
                                     },
                                 new Element()
                                     {
                                         Priority = 2,
                                         Description = "Third"
                                     }
                             };
elements.Sort();

Quindi il primo elemento è il secondo elemento precedentemente "Secondo". O, in altre parole, questa affermazione fallisce:

Assert.AreEqual("First", elements[0].Description);

Perché .NET riordina il mio elenco quando gli elementi sono essenzialmente gli stessi? Vorrei che riordinasse l'elenco solo se il confronto restituisce un valore diverso da zero.

Answer 1

Dalla documentazione del metodo List.Sort () da MSDN:

  

Questo metodo utilizza Array.Sort, che utilizza l'algoritmo QuickSort. Questa implementazione esegue un ordinamento instabile; cioè, se due elementi sono uguali, il loro ordine potrebbe non essere preservato. Al contrario, un ordinamento stabile preserva l'ordine degli elementi uguali.

Ecco il link: http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

Essenzialmente, l'ordinamento si comporta come progettato e documentato.

Answer 2

Ecco un metodo di estensione SortStable () per Elenco < T > dove T: IComparable < T > :

public static void SortStable<T>(this List<T> list) where T : IComparable<T>
{
    var listStableOrdered = list.OrderBy(x => x, new ComparableComparer<T>()).ToList();
    list.Clear();
    list.AddRange(listStableOrdered);
}

private class ComparableComparer<T> : IComparer<T> where T : IComparable<T>
{
    public int Compare(T x, T y)
    {
        return x.CompareTo(y);
    }
}

Prova:

[Test]
public void SortStable()
{
    var list = new List<SortItem>
                    {
                        new SortItem{ SortOrder = 1, Name = "Name1"},
                        new SortItem{ SortOrder = 2, Name = "Name2"},
                        new SortItem{ SortOrder = 2, Name = "Name3"},
                    };

    list.SortStable();

    Assert.That(list.ElementAt(0).SortOrder, Is.EqualTo(1));
    Assert.That(list.ElementAt(0).Name, Is.EqualTo("Name1"));
    Assert.That(list.ElementAt(1).SortOrder, Is.EqualTo(2));
    Assert.That(list.ElementAt(1).Name, Is.EqualTo("Name2"));
    Assert.That(list.ElementAt(2).SortOrder, Is.EqualTo(2));
    Assert.That(list.ElementAt(2).Name, Is.EqualTo("Name3"));
}

private class SortItem : IComparable<SortItem>
{
    public int SortOrder { get; set; }
    public string Name { get; set; }

    public int CompareTo(SortItem other)
    {
        return SortOrder.CompareTo(other.SortOrder);
    }
}

Nel metodo di test, se si chiama il metodo Sort () invece di SortStable (), si può vedere che il test fallirà.

Answer 3

Gli hai detto come confrontare le cose e lo ha fatto. Non fare affidamento sull'implementazione interna di Sort nell'applicazione. Ecco perché ti consente di ignorare CompareTo. Se vuoi avere un parametro di ordinamento secondario ("descrizione" in questo caso), codificalo nel tuo CompareTo. Affidarsi al modo in cui Sort funziona, è un ottimo modo per programmare un bug che è molto difficile da trovare.

È possibile trovare un quicksort stabile per .NET o utilizzare un merge sort (che è già stabile).

Answer 4

Vedi le altre risposte sul perché List.Sort () è instabile. Se hai bisogno di un ordinamento stabile e stai utilizzando .NET 3.5, prova Enumerable.OrderBy ( ) (LINQ).

Answer 5

Puoi risolvere questo problema aggiungendo un " valore indice " alla tua struttura e includendola nel metodo CompareTo quando Priority.CompareTo restituisce 0. Dovresti quindi inizializzare l'indice "indice". valore prima di fare l'ordinamento.

Il metodo CompareTo sarebbe simile al seguente:

public int CompareTo(Element other)
{
    var ret = Priority.CompareTo(other.Priority);
    if (ret == 0)
    {
        ret = Comparer<int>.Default.Compare(Index, other.Index);
    }
    return ret;
}

Quindi invece di fare elements.Sort () , dovresti:

for(int i = 0; i < elements.Count; ++i)
{
    elements[i].Index = i;
}
elements.Sort();

Answer 6

In alcune applicazioni, quando un elenco di articoli viene ordinato in base ad alcuni criteri, non è necessario preservare l'ordine originale degli articoli che si equivalgono. In altre applicazioni, è necessario. I metodi di ordinamento che preservano la disposizione degli elementi con chiavi corrispondenti (chiamati "ordinamenti stabili" sono generalmente molto più lenti di quelli che non lo fanno ("ordinamenti instabili"), oppure richiedono una notevole quantità di memoria temporanea (e sono ancora un po 'più lento). La prima routine di ordinamento "standard library" a diffondersi fu probabilmente la funzione qsort () inclusa nella libreria standard C. Quella libreria sarebbe stata frequentemente usata per ordinare elenchi di grandi dimensioni rispetto alla quantità totale di memoria disponibile. La libreria sarebbe stata molto meno utile se avesse richiesto una quantità di memoria temporanea proporzionale al numero di elementi nell'array da ordinare.

I metodi di ordinamento che verranno utilizzati in framework come Java o .net potrebbero praticamente utilizzare molto più spazio temporaneo di quanto sarebbe stato accettabile in una routine C qsort (). Un requisito di memoria temporanea pari alla dimensione dell'array da ordinare non costituirebbe nella maggior parte dei casi un problema particolare. Tuttavia, poiché è stato tradizionale per le biblioteche fornire un'implementazione di Quicksort, quello sembra essere il modello seguito da .net.

Answer 7

Se desideri ordinare in base a due campi anziché a uno, puoi farlo:

class Element : IComparable<Element>
{
    public int Priority { get; set; }
    public string Description { get; set; }

    public int CompareTo(Element other)
    {
        if (Priority.CompareTo(other.Priority) == 0)
        {
            return Description.CompareTo(other.Description);
        } else {
            return Priority.CompareTo(other.Priority);
        }
    }
}

Ovviamente, questo non soddisfa i requisiti di un algoritmo di ricerca stabile; Tuttavia, soddisfa la tua affermazione e consente il controllo del tuo ordine degli elementi in caso di uguaglianza.