Nel metodo dell'elenco .sort (), un elemento è mai paragonato a se stesso?

Question

Se passo in un ICOMparer personalizzato a un'istanza del metodo di Ordine () di un elenco, il metodo di confronto del confronto (x, y) verrà mai chiamato con lo stesso elemento?

cioè. È possibile che Compare(x,x) può essere chiamato.

Modificare: Più interessato al caso in cui si trovano gli elementi dell'elenco distinto.

Answer 1

Ho scritto un programma di test per provarlo. Sembra che in realtà fa Confronta () lo stesso elemento con se stesso (almeno confronta () è chiamato per lo stesso elemento due volte). In questo programma, confronta () 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'output è:

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

Answer 2

Dal Documenti:

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

QuickSort non confronterà mai un oggetto con se stesso. Alcune implementazioni di QuickSort confrontano gli articoli con se stessi. Ciò può accadere anche se quell'elemento si verifica più di una volta nella lista.

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

Answer 3

Sebbene non sia strettamente garantito, sono abbastanza sicuro che il metodo di ordinamento dell'elenco non chiamerà mai il metodo di confronto per confrontare un oggetto con se stesso a meno che quell'oggetto non appaia nell'elenco più volte. Baso questa conclusione sul fatto che List.sort è implementato utilizzando l'algoritmo QuickSort (secondo MSDN), che Non confronta mai di solito non comporta il confronto lo stesso elemento per se stesso (e nessuno dei due algoritmi di smistamento documentati a cui riesco a pensare). (Modifica: sembra che l'implementazione di Microsoft confronti l'elemento con se stessa. Vedi la risposta accettata sopra.)

Tuttavia, una buona pratica di codifica determinerebbe che l'implementazione ICOMparer dovrebbe essere in grado di gestire la sua approvata oggetto in entrambi i parametri, poiché altrimenti l'implementazione non è piena di ridimensionamento del contratto definito da ICOMparer. Probabilmente funzionerebbe per il tuo scenario, ma faresti affidamento sui dettagli dell'implementazione del metodo di ordinamento (che potrebbe cambiare in futuro) e non saresti in grado di utilizzare l'implementazione ICOMparer in altri scenari in cui non esiste un tale Garanzia (o peggio, tu o qualcun altro lo usi e possibilmente crea un bug difficile da trovare).

Answer 4

Un'altra risposta, questa basata su La parte XML di ECMA-335, le specifiche del BCL (Base Class Library). Sebbene non sia garantito per correggere ciò che fanno le attuali implementazioni, questo è tanto autorevole possibile. E la specifica non afferma altro che:

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

Sebbene ciò sia suggestivo per QuickSort, non è assolutamente una garanzia. Né le specifiche richiedono l'implementazione in termini di Array.Sort.

In conclusione: per quanto riguarda le specifiche, è perfettamente a posto per le implementazioni confrontare gli elementi con se stessi.