Array.Sort a stabilność sortowania

Funkcja Array.Sort sortuje tablicę elementów. Niestety algorytm jest niestabilny co nie zawsze jest dobrym rozwiązaniem. Rozważmy poniższy kod:

public class Person
{        
   public int Age { get; set; }
   public string Name { get; set; }
}

internal class Program
{
   public static void Main()
   {

       var persons = new[] {
       new Person { Age = 1, Name = "a" },
       new Person { Age = 2, Name = "b" },
       new Person { Age = 3, Name = "c" },
       new Person { Age = 2, Name = "e" },
       new Person { Age = 1, Name = "f" },
       new Person { Age = 4, Name = "g" },
       new Person { Age = 1, Name = "h" },
   };
       
       Array.Sort(persons, (p1, p2) => p1.Age.CompareTo(p2.Age));
       foreach (var person in persons)
       {
           Console.WriteLine("{0}:{1}", person.Name, person.Age);
       }
   }
}

W stabilnych algorytmach jeśli mamy sekwencję (3,’a’), (5,’b’), (3,’c’) i posortujemy ją po pierwszym kluczu to na wyjściu zawsze będzie (3,’a’),(3,’c’), (5,’b’). W niestabilnych może okazać się, że dostaniemy (3,’c’), (3,’a’),  (5,’b’). Matematycznie jest to jak najbardziej poprawne ale już w interfejsach użytkownika nie zawsze jest to pożądany efekt. Innymi słowy, kolejność kluczy nie jest zachowywana. Jednym z rozwiązań jest użycie LINQ i funkcji OrderBy, które zawsze wykonują stabilne sortowanie. Jeśli jednak upieramy się przy Array.Sort możemy użyć własnego Comparer’a (źródło forum StackOverFlow):

public class Person
{
   public int Age { get; set; }
   public string Name { get; set; }
}
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);
       }
   }
}
internal class Program
{
   public static void Main()
   {

       var persons = new[]
                         {
                             new Person {Age = 1, Name = "a"},
                             new Person {Age = 2, Name = "b"},
                             new Person {Age = 3, Name = "c"},
                             new Person {Age = 2, Name = "e"},
                             new Person {Age = 1, Name = "f"},
                             new Person {Age = 4, Name = "g"},
                             new Person {Age = 1, Name = "h"},
                         };

       persons.StableSort((p1, p2) => p1.Age.CompareTo(p2.Age));
       foreach (var person in persons)
       {
           Console.WriteLine("{0}:{1}", person.Name, person.Age);
       }
   }
}

Metoda Array.Sort przyjmuje również tablicę kluczy. Dzięki niej jesteśmy w stanie zachować kolejność, gdy dwa klucze są takie same. Oczywiście gdy wszystkie wartości są różne od siebie wtedy nie ma problemu ze stabilnością, ponieważ kolejność może być tylko jedna…

10 thoughts on “Array.Sort a stabilność sortowania”

  1. Zaproponowane rozwiązanie jest o tyle słabe ze wzrasta złożoność obliczeniowa (gdyż przed posortowaniem należy przejść dodatkowo całą tablicę w celu wygenerowania identyfikatorów). Proponuję raczej moje rozwiązanie http://stackoverflow.com/a/14849554/2067637, które stabilizuję Sort względem HashCode (nie jest to może najlepsze rozwiązanie, ale nie zmienia złożoności i wielu przypadkach wystarczająco stabilizuje sortowanie).

  2. Co do przejscia tablicy to jest to tylko +n do zlozonosci. Czyli jak miales nlogn bedziesz mial nlog+n co nie jest jakims wielkim problemem.
    Co do zaproponowanego przez Ciebie rozwiazania to moim zdaniem jest niepoprawne. GetHashCode przeciez nie ma nic wspolnego z kolejnoscia w kolekcji w jakiej znajduje sie.

  3. “Co do zaproponowanego przez Ciebie rozwiazania to moim zdaniem jest niepoprawne. GetHashCode przeciez nie ma nic wspolnego z kolejnoscia w kolekcji w jakiej znajduje sie.”

    Tak, ale tu chodzi o zapewnienie stabilności (jak w opisanym wyżej algorytmie), a w tym przypadku elementy zawsze będzie (3,’a’),(3,’c’), (5,’b’).
    bo HashCode dla (3,’a’) i dla (3,’c’) będzie różny (oczywiście mówimy o sytuacji gdy HashCode jest zaimplementowany poprawnie) a gdy zdublujesz element to masz równe HashCode. Problem pojawia się dopiero w sytuacji gdy elementy są różne referencyjnie, a mają takie same HashCode. Jednak wiele algorytmów .NET opiera swoje działanie na porównywaniu hashy jak choćby .GroupBy(), .Distinct(). Poza tym GetHashCode jest tu używany nie do ustalenia kolejnośći a do rozróżnienia elementów porównywanych czyli stałego uszeregowania pomiędzy (3,’a’) i (3,’c’)

  4. “miales nlogn bedziesz mial nlog+n co nie jest jakims wielkim problemem.” Eee tam, nie mówię że to problem, tylko że wolę rozwiązanie z HashCode’ami (bo w ogólności zadziała), bo nie wpływają na złożoność.

  5. Probowalem cos takiego i wynik jest niepoprawny:
    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” },

    };
    Comparison comparison = (x, y) => x.BirthYear.CompareTo(y.BirthYear);
    Array.Sort(unsorted, comparison.WithGetHashCode());
    foreach (var person in unsorted)
    {
    Console.WriteLine(“{0}:{1}”, person.Name, person.BirthYear);
    }

    }
    }
    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;
    };
    }
    }
    sealed class Person
    {
    public int BirthYear { get; set; }
    public string Name { get; set; }

    public override bool Equals(object obj)
    {
    if (ReferenceEquals(null, obj)) return false;
    if (ReferenceEquals(this, obj)) return true;
    if (obj.GetType() != typeof (Person)) return false;
    return Equals((Person) obj);
    }

    public bool Equals(Person other)
    {
    if (ReferenceEquals(null, other)) return false;
    if (ReferenceEquals(this, other)) return true;
    return other.BirthYear == BirthYear && Equals(other.Name, Name);
    }

    public override int GetHashCode()
    {
    unchecked
    {
    return (BirthYear*397) ^ (Name != null ? Name.GetHashCode() : 0);
    }
    }
    }

  6. Kurcze naprawdę nie widzę tego czemu wynik jest nie poprawny. Uruchomiłem i sortuje dobrze (ale to nie dowód), dowodem byłoby niestabilne zachowanie (czyli różne kolejność przy tych samych danych).

    Pokaż mi proszę w jakim przypadku będzie niestabilnie. Czyli np. w jaki przypadku kolejność dla dat urodzin 1955 (lub 1948) będzie inna.

  7. No i co to przeszkadza ? Przecież dla StableSort jest tak samo (nawet gdyby nie było nie ma to znaczenia). Przecież “Jean Reno” i “Kathy Bates” mają tą samą datę urodzin więc bez znaczenia czy wpierw będzie “Reno” czy “Bates”. Znaczenia ma za to czy “Reno” ZAWSZE będzie przed “Bates” (po mojemu zawsze). To “zawsze” stanowi przecież o stabilności, a nie kolejność w jakiej ustawione jest “Reno” i “Bates”.

  8. Ok, masz rację. Teraz widzę swój błąd. Za wiki “Elementy o równej wartości będą występowały, po posortowaniu, w takiej samej kolejności jaką miały w zbiorze nieposortowanym.”. Kluczem jest tu “w takiej samej kolejności jaką miały w zbiorze nieposortowanym”, moja poprawka tego nie zapewnia. Moim błędem było mylne założenie że istotne jest by wynik był zawsze taki sam. Twoja racja. Pozdrawiam i dzięki.

  9. Nom:) Dodam tylko, ze kod przedstawioy na stackoverflow albo w moim poscie zachowuje zawsze kolejnosc tak ze Jean Reno jest zawsze po Kathy Bates.

Leave a Reply

Your email address will not be published.