Czy istnieje sposób sprawdzenia, jak posortowana jest lista?

Chodzi mi o to, że nie chodzi o to, aby wiedzieć, czy lista jest posortowana, czy nie (boolean), ale coś w rodzaju współczynnika „sortowania”, czegoś w rodzaju współczynnika korelacji w statystyce.

Na przykład,

• Jeśli pozycje na liście są w porządku rosnącym, to jej kurs wyniesie 1,0

• Jeśli lista jest posortowana malejąco, jej współczynnik wyniesie -1,0

• Jeśli lista jest prawie posortowana rosnąco, jej współczynnik wyniesie 0,9 lub jakąś wartość bliską 1.

• Jeśli lista nie jest w ogóle posortowana (losowa), jej współczynnik byłby bliski 0

Piszę małą bibliotekę w Scali do ćwiczeń. Myślę, że przydałby się współczynnik sortowania, ale nie znajduję żadnych informacji o czymś takim. Może nie znam odpowiednich terminów na to pojęcie.

Możesz po prostu policzyć liczbę inwersji na liście.

Odwrócenie

Odwrócenie w ciągu elementów typu Tto para elementów sekwencji, które pojawiają się nie w porządku według pewnego uporządkowania <na zbiorze elementów T.

Z Wikipedii :

Formalnie niech A(1), A(2), ..., A(n)będzie ciągiem nliczb.
Jeśli i < ji A(i) > A(j), wtedy para (i,j)nazywany jest odwrócenie się A.

Liczba inwersji sekwencji jest jedną z powszechnych miar sortowania.
Formalnie liczba inwersji jest definiowana jako liczba inwersji, to znaczy

Aby wyjaśnić te definicje, rozważ przykładową sekwencję 9, 5, 7, 6. Ta sekwencja ma inwersje (0,1), (0,2), (0,3), (2,3) i numer inwersji 4 .

Jeśli chcesz uzyskać wartość między 0a 1, możesz podzielić liczbę inwersji przez N choose 2.

Aby faktycznie utworzyć algorytm obliczający ten wynik dla posortowania listy, masz dwa podejścia:

Podejście 1 (deterministyczne)

Zmodyfikuj swój ulubiony algorytm sortowania, aby śledzić, ile inwersji koryguje podczas działania. Chociaż jest to nietrywialne i ma różne implementacje w zależności od wybranego algorytmu sortowania, otrzymasz algorytm, który nie jest droższy (pod względem złożoności) niż algorytm sortowania, od którego zacząłeś.

Jeśli wybierzesz tę trasę, pamiętaj, że nie jest to tak proste, jak liczenie „zamiany”. Na przykład scalanie jest najgorszym przypadkiem O(N log N), ale jeśli zostanie uruchomione na liście posortowanej w porządku malejącym, poprawi wszystkie N choose 2inwersje. To jest O(N^2)odwrócenie poprawione w O(N log N)operacjach. Dlatego niektóre operacje muszą nieuchronnie korygować więcej niż jedną inwersję naraz. Musisz uważać na swoją implementację. Uwaga: możesz to zrobić ze O(N log N)złożonością, to po prostu trudne.

Powiązane: obliczanie liczby „inwersji” w permutacji

Podejście 2 (stochastyczne)

• Losowe pary próbek (i,j), gdziei != j
• Dla każdej pary określ, czy list[min(i,j)] < list[max(i,j)](0 czy 1)
• Oblicz średnią z tych porównań, a następnie znormalizuj według N choose 2

Osobiście wybrałbym podejście stochastyczne, chyba że masz wymóg dokładności - choćby dlatego, że jest tak łatwy do wdrożenia.

Jeśli naprawdę potrzebujesz wartości ( z') między -1(posortowane malejąco) do 1(posortowane rosnąco), możesz po prostu zmapować wartość powyżej ( z), która znajduje się pomiędzy 0(posortowano rosnąco) i 1(posortowano malejąco), na ten zakres przy użyciu tej formuły :

z' = -2 * z + 1

Tradycyjną miarą sortowania listy (lub innej struktury sekwencyjnej) jest liczba inwersji.

Liczba inwersji to liczba par (a, b). Indeks a <b ORAZ b <<a. W tym celu <<reprezentuje dowolną relację porządkową wybraną dla określonego rodzaju.

W pełni posortowana lista nie zawiera inwersji, a całkowicie odwrócona lista ma maksymalną liczbę inwersji.

Możesz użyć rzeczywistej korelacji.

Załóżmy, że każdemu elementowi na posortowanej liście przypisujesz liczbę całkowitą, zaczynając od zera. Zwróć uwagę, że wykres wskaźnika pozycji elementów w funkcji rangi będzie wyglądał jak kropki w linii prostej (korelacja 1,0 między pozycją a pozycją).

Możesz obliczyć korelację na tych danych. W przypadku sortowania odwrotnego otrzymasz -1 i tak dalej.

Były świetne odpowiedzi i chciałbym dodać matematyczny aspekt dla kompletności:

• Posortowaną listę można zmierzyć, mierząc, w jakim stopniu jest ona skorelowana z posortowaną listą. Aby to zrobić, możesz użyć korelacji rang (najbardziej znanej jest korelacja Spearmana ), która jest dokładnie taka sama jak zwykła korelacja, ale używa rangi elementów na liście zamiast wartości analogowych jej elementów.

• Istnieje wiele rozszerzeń, takich jak współczynnik korelacji (+1 dla dokładnego sortowania, -1 dla dokładnej inwersji)

• Pozwala to mieć właściwości statystyczne dla tej miary, takie jak permutacyjne centralne twierdzenie graniczne, które pozwala poznać rozkład tej miary dla list losowych.

Oprócz liczby inwersji, w przypadku list numerycznych można sobie wyobrazić średnią kwadratową odległość od posortowanego stanu:

#! ruby
d = -> a { a.zip( a.sort ).map { |u, v| ( u - v ) ** 2 }.reduce( :+ ) ** 0.5 }

a = 8, 7, 3, 4, 10, 9, 6, 2, 5, 1
d.( a ) #=> 15.556
d.( a.sort ) #=> 0.0
d.( a.sort.reverse ) # => 18.166 is the worrst case

Nie jestem pewien "najlepszej" metody, ale prostą metodą byłoby porównanie każdego elementu z kolejnym, zwiększając licznik, jeśli element2> element 1 (lub cokolwiek chcesz przetestować), a następnie podzielenie przez całkowitą liczbę elementów. Powinien dać ci procent.

Policzyłbym porównania i podzieliłbym je na całkowitą liczbę porównań. Oto prosty przykład w języku Python .

my_list = [1,4,5,6,9,-1,5,3,55,11,12,13,14]

right_comparison_count = 0

for i in range(len(my_list)-1):
    if my_list[i] < my_list[i+1]: # Assume you want to it ascending order
        right_comparison_count += 1

if right_comparison_count == 0:
    result = -1
else:
    result = float(right_comparison_count) / float((len(my_list) - 1))

print result

A może coś takiego?

#!/usr/bin/python3

def sign(x, y):
   if x < y:
      return 1
   elif x > y:
      return -1
   else:
      return 0

def mean(list_):
   return float(sum(list_)) / float(len(list_))

def main():
   list_ = [ 1, 2, 3, 4, 6, 5, 7, 8 ]
   signs = []
   # this zip is pairing up element 0, 1, then 1, 2, then 2, 3, etc...
   for elem1, elem2 in zip(list_[:-1], list_[1:]):
      signs.append(sign(elem1, elem2))

   # This should print 1 for a sorted list, -1 for a list that is in reverse order
   # and 0 for a run of the same numbers, like all 4's
   print(mean(signs))

main()

Jeśli weźmiesz swoją listę, obliczysz rangi wartości na tej liście i wywołaj listę rang Yoraz inną listę, Xktóra zawiera liczby całkowite od 1do length(Y), możesz uzyskać dokładnie taką miarę sortowania, której szukasz, obliczając współczynnik korelacji , rmiędzy dwiema listami.

r = \frac{\sum ^n _{i=1}(X_i - \bar{X})(Y_i - \bar{Y})}{\sqrt{\sum ^n _{i=1}(X_i - \bar{X})^2} \sqrt{\sum ^n _{i=1}(Y_i - \bar{Y})^2}} 

W przypadku w pełni posortowanej listy,, w przypadku listy posortowanej r = 1.0odwrotnie r=-1.0, i rwaha się między tymi limitami dla różnych stopni sortowania .

Możliwym problemem związanym z tym podejściem, w zależności od aplikacji, jest to, że obliczenie rangi każdego elementu na liście jest równoważne jego sortowaniu, więc jest to operacja O (n log n).