Nel metodo List <T> .Sort(), un oggetto è mai paragonato a se stesso?

Question

Se si passa un IComparer personalizzato a un'istanza del metodo Sort() di una lista, il metodo Compare (x, y) del comparatore verrà mai chiamato con lo stesso elemento?

ie. È possibile che sia possibile chiamare Compare(x,x).

Modifica: Più interessati al caso in cui gli elementi della lista sono distinti.

Answer 1

Ho scritto un programma di prova per provarlo. Sembra che in realtà fa Compare() lo stesso elemento a sé stesso (almeno Compare() viene chiamato per lo stesso elemento due volte). In questo programma, Compare() viene chiamato con argomenti (2, 2).

using System; 
using System.Collections.Generic; 

static class Program 
{ 
    class MyComparer : Comparer<int> 
    { 
     public override int Compare(int x, int y) 
     { 
      Console.WriteLine("Compare(" + x + ", " + y + ")"); 
      if (x < y) return -1; 
      if (x > y) return 1; 
      return 0; 
     } 
    } 

    static void Main() 
    { 
     MyComparer comparer = new MyComparer(); 
     List<int> list = new List<int> { 1, 2, 3 }; 
     list.Sort(comparer); 
     return; 

    } 
} 

e l'uscita è:

Compare(1, 2) 
Compare(1, 3) 
Compare(2, 3) 
Compare(1, 2) 
Compare(2, 2) 
Compare(2, 3) 
Compare(2, 2) 

Answer 2

Dal docs:

Questo metodo utilizza Array.Sort, che utilizza l'algoritmo QuickSort.

QuickSort non confronta mai un oggetto con se stesso. Alcune implementazioni di QuickSort mettono a confronto gli oggetti. Questo può accadere anche se quell'elemento si verifica più di una volta nel tuo Elenco.

In entrambi i casi, affinché la funzione di confronto sia una funzione di confronto corretta e ben funzionante, è necessario gestire il caso di elementi confrontati a se stessi.

Answer 3

Sebbene non sia strettamente garantito, sono abbastanza sicuro che il metodo Sort di List non chiamerà mai il metodo di confronto per confrontare un oggetto con se stesso a meno che l'oggetto non appaia nell'elenco più volte. Baso questa conclusione sul fatto che ListSort è implementato usando l'algoritmo QuickSort (secondo MSDN), che non confronta mai di solito non comporta il confronto di lo stesso elemento a se stesso (e nessuno dei due altro ordinamento documentato algoritmi a cui riesco a pensare). (Modifica: Sembra che l'implementazione di Microsoft confronti l'elemento a se stesso. Vedere risposta accettata sopra.)

Tuttavia, una buona pratica di codifica imporrebbe che l'implementazione di IComparer debba essere in grado di gestire lo stesso oggetto in entrambi i parametri, altrimenti l'implementazione non è completa del contratto definito da IComparer. Probabilmente funzionerebbe per il tuo scenario, ma dovresti fare affidamento sui dettagli di implementazione del metodo di ordinamento (che potrebbero cambiare in futuro) e non potresti utilizzare l'implementazione di IComparer in altri scenari in cui non esiste tale garanzia (o peggio, tu o qualcun altro lo usa e probabilmente crea un bug difficile da trovare).

Answer 4

Un'altra risposta, questa volta sulla base the XML part of ECMA-335, la specifica del BCL (Base Class Library). Anche se non è garantito il collegamento con le effettive implementazioni, questo è autorevole. E la specifica non dice nient'altro:

Nel peggiore dei casi, questa operazione è O (n^2), dove n è il numero di elementi da ordinare. In media è O (n log n).

Sebbene questo sia indicativo di QuickSort, non è assolutamente garantito. Né le specifiche richiedono implementazione in termini di Array.Sort.

Bottom line: per quanto riguarda le specifiche, è perfettamente accettabile per le implementazioni di confrontare gli elementi a se stessi.