Jak zmierzyć „sortowanie”

34

Zastanawiam się, czy istnieje standardowy sposób pomiaru „sortowania” tablicy? Czy tablicę z medianą liczby możliwych inwersji można uznać za maksymalnie nieposortowaną? Rozumiem przez to, że jest to w zasadzie tak daleko, jak to możliwe, od sortowania lub odwrotnego sortowania.

Robert S. Barnes
źródło

Odpowiedzi:

31

Nie, to zależy od twojej aplikacji. Miary sortowania są często określane jako miary nieporządku , które są funkcjami od do , gdzie jest zbiorem wszystkich skończonych sekwencji różnych nieujemnych liczb całkowitych. Badanie Estivill-Castro i Wood [1] wymienia i omawia 11 różnych miar zaburzeń w kontekście algorytmów sortowania adaptacyjnego. R N < NN<NRN<N

Liczba inwersji może działać w niektórych przypadkach, ale czasami jest niewystarczająca. Przykładem podanym w [1] jest sekwencja

n/2+1,n/2+2,,n,1,,n/2

ma kwadratową liczbę inwersji, ale składa się tylko z dwóch rosnących serii. Jest prawie posortowane, ale nie jest to uchwycone przez inwersje.


[1] Estivill-Castro, Vladmir i Derick Wood. „Przegląd algorytmów adaptacyjnego sortowania”. ACM Computing Surveys (CSUR) 24.4 (1992): 441–476.

Juho
źródło
2
Kontekst próbuje zrozumieć, dlaczego Quicksort działa stosunkowo słabo w przypadkowych kombinacjach n elementów, w których liczba inwersji jest zbliżona do mediany.
Robert S. Barnes
1
Świetny przykład, dokładnie takich informacji szukałem.
Robert S. Barnes,
1
Estivill-Castro i Drewno jest odniesienie do tego na pewno.
Pedro Dusso
10

Mannila [1] aksomatyzuje uprzedzanie (z naciskiem na algorytmy porównawcze) w następujący sposób (parafrazowanie).

Niech jest kompletnie zamówionym zestawem. Następnie odwzorowanie z (sekwencje odrębnych elementów z ) na naturals jest miarą uprzedzenia, jeśli spełnia poniższe warunki.m Σ ΣΣmΣΣ

  1. Jeśli posortowane jest to . m ( X ) = 0XΣm(X)=0

  2. Jeśli z , i dla wszystkich , następnie .X,YΣX=x1xnY=y1ynxi<xiyi<yji,j[1..n]m(X)=m(Y)

  3. Jeśli jest podsekwencją , to .XYΣm(X)m(Y)

  4. Jeśli dla wszystkich i dla niektórych , to .xi<yji[1..|X|]j[1..|Y|]X,YΣm(XY)m(X)+m(Y)

  5. m(aX)|X|+m(X) dla wszystkich i .XΣaEX

Przykładami takich środków są:

  • liczba inwersji,
  • liczba zamian,
  • liczba elementów, które nie są maksymami od lewej do prawej, oraz
  • długość najdłużej rosnącego podsekwencji (odejmowana od długości wejściowej).

Zauważ, że losowe rozkłady wykorzystujące te miary zostały zdefiniowane, tj. Takie, które sprawiają, że sekwencje, które są mniej lub bardziej posortowane, są mniej lub bardziej prawdopodobne. Są to tak zwane rozkłady podobne do Ewensa [2, Ch. 4–5; 3, przykład 12; 4], którego szczególnym przypadkiem jest tak zwana dystrybucja Mallowsa . Wagi są parametryczne w stałej i spełniająθ>0

Pr(X)=θm(X)YΣΣ|X|θm(Y) .

Zwróć uwagę, jak definiuje rozkład równomierny (dla wszystkich ).mθ=1m

Ponieważ możliwe jest skuteczne próbkowanie permutacji w tych pomiarach, ta część pracy może być przydatna w praktyce podczas algorytmów sortowania porównawczego.


  1. Miary uprzedzeń i optymalne algorytmy sortowania autorstwa H. Mannili (1985)
  2. Logarytmiczne struktury kombinatoryczne: podejście probabilistyczne R. Arratia, AD Barbour i S. Tavaré (2003)
  3. O dodaniu listy liczb (i innych jedno-zależnych procesów determinujących) autorstwa A. Borodina, P. Diaconisa i J. Fulmana (2010)
  4. Rozkłady podobne do Ewensa i analiza algorytmów N. Auger i in. (2016)
Raphael
źródło
3

Mam własną definicję „sortowania” sekwencji.

Przy dowolnej sekwencji [a, b, c,…] porównujemy ją z posortowaną sekwencją zawierającą te same elementy, liczymy liczbę dopasowań i dzielimy ją przez liczbę elementów w sekwencji.

Na przykład w podanej kolejności [5,1,2,3,4]postępujemy w następujący sposób:

1) posortuj sekwencję: [1,2,3,4,5]

2) porównaj posortowaną sekwencję z oryginałem, przesuwając ją o jedną pozycję na raz i licząc maksymalną liczbę dopasowań:

        [5,1,2,3,4]
[1,2,3,4,5]                            one match

        [5,1,2,3,4]
  [1,2,3,4,5]                          no matches

        [5,1,2,3,4]
    [1,2,3,4,5]                        no matches

        [5,1,2,3,4]
      [1,2,3,4,5]                      no matches

        [5,1,2,3,4]
        [1,2,3,4,5]                    no matches

        [5,1,2,3,4]
          [1,2,3,4,5]                  4 matches

        [5,1,2,3,4]
            [1,2,3,4,5]                no matches

                ...

         [5,1,2,3,4]
                 [1,2,3,4,5]            no matches

3) Maksymalna liczba dopasowań wynosi 4, możemy obliczyć „sortowanie” jako 4/5 = 0,8.

Sortowanie posortowanej sekwencji wynosi 1, a sortowanie sekwencji z elementami umieszczonymi w odwrotnej kolejności - 1 / n.

Ideą tej definicji jest oszacowanie minimalnej ilości pracy, którą musielibyśmy zrobić, aby przekonwertować dowolną sekwencję na posortowaną sekwencję. W powyższym przykładzie musimy przesunąć tylko jeden element, 5 (istnieje wiele sposobów, ale przesunięcie 5 jest najbardziej wydajne). Gdyby elementy były umieszczone w odwrotnej kolejności, musielibyśmy przenieść 4 elementy. A po uporządkowaniu sekwencji nie jest wymagana żadna praca.

Mam nadzieję, że moja definicja ma sens.

Andrushenko Alexander
źródło
Dobry pomysł. Podobną definicją jest Exc, trzecia definicja nieporządku w artykule wymienionym w odpowiedzi Juho . Exc jest liczbą operacji wymaganych do zmiany kolejności sekwencji na posortowane.
Apass.Jack
Cóż, być może właśnie zastosowałem moje zrozumienie entropii i nieładu do sekwencji elementów :-)
Andrushenko Alexander
-2

Jeśli potrzebujesz czegoś szybkiego i brudnego (przerażają mnie znaki sumowania) napisałem w C ++ super łatwą funkcję nieporządku dla klasy o nazwie Array, która generuje tablice int wypełnione losowo generowanymi liczbami:

void Array::disorder() {
    double disorderValue = 0;
    int counter = this->arraySize;
    for (int n = 0; n < this->arraySize; n++) {
        disorderValue += abs(((n + 1) - array[n]));
//      cout << "disorderValue variable test value = " << disorderValue << endl;
        counter++;
    }
    cout << "Disorder Value = " << (disorderValue / this->arraySize) / (this->arraySize / 2) << "\n" << endl;
}

Funkcja po prostu porównuje wartość w każdym elemencie z indeksem elementu + 1, dzięki czemu tablica w odwrotnej kolejności ma wartość nieuporządkowania równą 1, a posortowana tablica ma wartość nieuporządkowania równą 0. Nie jest to skomplikowane, ale działa.

Michał

Michael Sneberger
źródło
To nie jest strona programistyczna. Wystarczyłoby zdefiniować pojęcie nieporządku i wspomnieć, że można go obliczyć w czasie liniowym.
Yuval Filmus,