Jak zmierzyć „sortowanie”

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.

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 < $N^{<N}$$\mathbb{R}$$N^{<N}$

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

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.

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 Σ ⋆$\Sigma$$m$$\Sigma^{\star}$$\Sigma$

1. Jeśli posortowane jest to . m ( X ) = $X \in \Sigma^{\star}$$m(X) = 0$

2. Jeśli z , i dla wszystkich , następnie .$X,Y \in \Sigma^{\star}$$X = x_1 \dots x_n$$Y = y_1 \dots y_n$$x_i < x_i \iff y_i < y_j$$i,j \in [1..n]$$m(X) = m(Y)$

3. Jeśli jest podsekwencją , to .$X$$Y \in \Sigma^{\star}$$m(X) \leq m(Y)$

4. Jeśli dla wszystkich i dla niektórych , to .$x_i < y_j$$i \in [1..|X|]$$j \in [1..|Y|]$$X,Y \in \Sigma^{\star}$$m(X \cdot Y) \leq m(X) + m(Y)$

5. $m(a \cdot X) \leq |X| + m(X)$ dla wszystkich i .$X \in \Sigma^{\star}$$a \in E \setminus X$

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ą$\theta > 0$

$\qquad\displaystyle \operatorname{Pr}(X) = \frac{\theta^{\,m(X)}}{\sum_{Y \in \Sigma^{\star} \cap \Sigma^{|X|}} \theta^{\,m(Y)}}$ .

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

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)

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.

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ł