Gibt es eine Möglichkeit zu messen, wie sortiert eine Liste ist?

161

Gibt es eine Möglichkeit zu messen, wie sortiert eine Liste ist?

Ich meine, es geht nicht darum zu wissen, ob eine Liste sortiert ist oder nicht (boolesch), sondern um ein Verhältnis von "Sortierung", so etwas wie den Korrelationskoeffizienten in der Statistik.

Beispielsweise,

  • Wenn die Elemente einer Liste in aufsteigender Reihenfolge vorliegen, beträgt ihre Rate 1,0

  • Wenn die Liste absteigend sortiert ist, beträgt ihre Rate -1,0

  • Wenn die Liste fast aufsteigend sortiert ist, beträgt ihre Rate 0,9 oder einen Wert nahe 1.

  • Wenn die Liste überhaupt nicht sortiert ist (zufällig), liegt ihre Rate nahe bei 0

Ich schreibe eine kleine Bibliothek in Scala zum Üben. Ich denke, eine Sortierrate wäre nützlich, aber ich finde keine Informationen über so etwas. Vielleicht kenne ich keine angemessenen Begriffe für das Konzept.

Josell
quelle
4
Würde dies verwendet, um den idealen Algorithmus zum Sortieren der Liste zu bestimmen? Zum Beispiel wäre QuickSort für Werte nahe 0 ideal, aber Werte an beiden Enden der Skala (nahezu sortiert oder nahezu umgekehrt sortiert), MergeSort wäre viel schneller, da die Qualitätskontrolle in diesen Fällen auf O (N ^ 2) übergeht.
Darrel Hoffman
8
+1 für "Verhältnis der Sortierung"
0x499602D2
1
@Fuhrmanator Die stochastische Version des Algorithmus muss keine Sortierung durchführen, um zu einer probabilistischen Schätzung der Sortierung zu gelangen. Nur wenn Sie ein genaues Maß erhalten möchten , müssen Sie eine Sortierung durchführen.
Timothy Shields
1
Sarkastischer, aber lustiger erster Instinkt: Sie können die Liste einfügen und sehen, wie lange es dauert, und diese dann mit der Zeit vergleichen, die zum Sortieren der (jetzt sortierten) Liste und umgekehrt benötigt wird.
kqr

Antworten:

142

Sie können einfach die Anzahl der Inversionen in der Liste zählen.

Inversion

Eine Inversion in einer Folge von Elementen des Typs Tist ein Paar von Folgeelementen, die gemäß einer bestimmten Reihenfolge <auf der Menge von T's in der falschen Reihenfolge erscheinen .

Aus Wikipedia :

Formell sei A(1), A(2), ..., A(n)eine Folge von nZahlen.
Wenn i < jund A(i) > A(j), dann heißt das Paar (i,j)eine Inversion von A.

Die Inversionsnummer einer Sequenz ist ein gängiges Maß für ihre Sortierung.
Formal wird die Inversionszahl als die Anzahl der Inversionen definiert, d. H.

Definition

Betrachten Sie die Beispielsequenz, um diese Definitionen klarer zu machen 9, 5, 7, 6. Diese Sequenz hat die Inversionen (0,1), (0,2), (0,3), (2,3) und die Inversionsnummer 4 .

Wenn Sie einen Wert zwischen 0und möchten 1, können Sie die Inversionszahl durch dividieren N choose 2.

Um tatsächlich einen Algorithmus zum Berechnen dieser Punktzahl für die Sortierung einer Liste zu erstellen, haben Sie zwei Ansätze:

Ansatz 1 (deterministisch)

Ändern Sie Ihren bevorzugten Sortieralgorithmus, um zu verfolgen, wie viele Inversionen während der Ausführung korrigiert werden. Obwohl dies nicht trivial ist und je nach ausgewähltem Sortieralgorithmus unterschiedliche Implementierungen aufweist, erhalten Sie einen Algorithmus, der (in Bezug auf die Komplexität) nicht teurer ist als der Sortieralgorithmus, mit dem Sie begonnen haben.

Wenn Sie diesen Weg einschlagen, beachten Sie, dass es nicht so einfach ist, "Swaps" zu zählen. Mergesort ist beispielsweise der schlimmste Fall O(N log N). Wenn es jedoch in einer Liste ausgeführt wird, die in absteigender Reihenfolge sortiert ist, werden alle N choose 2Inversionen korrigiert . Das sind O(N^2)Inversionen, die im O(N log N)Betrieb korrigiert wurden. Daher müssen einige Operationen zwangsläufig mehr als eine Inversion gleichzeitig korrigieren. Sie müssen mit Ihrer Implementierung vorsichtig sein. Hinweis: Sie können dies mit O(N log N)Komplexität tun , es ist nur schwierig.

Verwandte: Berechnung der Anzahl der "Inversionen" in einer Permutation

Ansatz 2 (stochastisch)

  • Zufällige Stichprobenpaare (i,j), wobeii != j
  • Bestimmen Sie für jedes Paar, ob list[min(i,j)] < list[max(i,j)](0 oder 1)
  • Berechnen Sie den Durchschnitt dieser Vergleiche und normalisieren Sie dann um N choose 2

Ich persönlich würde mich für den stochastischen Ansatz entscheiden, es sei denn, Sie haben ein Erfordernis der Genauigkeit - schon allein deshalb, weil es so einfach zu implementieren ist.


Wenn Sie wirklich einen Wert ( z') zwischen -1(sortiert absteigend) bis 1(sortiert aufsteigend) möchten , können Sie den Bereich über ( z), der zwischen 0(sortiert aufsteigend) und 1(sortiert absteigend) liegt, mit dieser Formel einfach diesem Bereich zuordnen ::

z' = -2 * z + 1
Timothy Shields
quelle
2
Es ist faszinierend für mich, dass das Sortieren einer Liste (normalerweise) O (n * logn) ist und die naive / offensichtliche Methode zur Berechnung von Inversionen O (n ^ 2) ist. Ich frage mich, ob es bessere Algorithmen gibt, um die Anzahl der Inversionen zu berechnen.
Mark Bessey
5
In dieser SO-Frage gibt es einige interessante Ansätze: stackoverflow.com/questions/6523712/… Grundsätzlich läuft es darauf hinaus , das Array zu sortieren, um herauszufinden, wie viele Inversionen es gibt.
Mark Bessey
4
Ich dachte naiv, man könnte nur benachbarte Paare zählen, die nicht in Ordnung sind. Aber das wird stark unterzählen: 1 2 3 1 2 3 hat nur eine benachbarte Inversion, aber es ist 50% invertiert durch das korrektere Maß.
Barmar
2
@Barmar Ich denke, dass Liste 1 2 3 1 2 3 als sortiert sortiert qualifizieren würde
;-)
2
@ TimothyShields, na ja, nein, das ist es nicht. Aber ich werde den Punkt nicht näher erläutern. Nur ein Vorschlag, eine nicht formale Definition hinzuzufügen, die für weniger symbolisch geneigte Personen zugänglicher ist.
Chris Calo
24

Das traditionelle Maß dafür, wie sortiert eine Liste (oder eine andere sequentielle Struktur) ist, ist die Anzahl der Inversionen.

Die Anzahl der Inversionen ist die Anzahl der Paare (a, b) des Index von a <b UND b <<a. Für diese Zwecke steht <<für jede Bestellbeziehung, die Sie für Ihre bestimmte Sorte wählen.

Eine vollständig sortierte Liste enthält keine Inversionen, und eine vollständig umgekehrte Liste enthält die maximale Anzahl von Inversionen.

Marcin
quelle
5
Technisch 5 4 3 2 1ist vollständig sortiert, da die Reihenfolge nicht angegeben ist, aber ich bin pedantisch :-)
paxdiablo
7
@paxdiablo Das hängt von der Definition von ab <.
Marcin
@paxdiablo, man könnte die Sortierung an der Entfernung von der Anzahl der Inversionen bis zur nächsten von 0 oder messen n choose 2.
Huon
17

Sie können die tatsächliche Korrelation verwenden.

Angenommen, Sie weisen jedem Element in der sortierten Liste einen ganzzahligen Rang ab Null zu. Beachten Sie, dass ein Diagramm des Positionsindex der Elemente gegenüber dem Rang wie Punkte in einer geraden Linie aussieht (Korrelation von 1,0 zwischen Position und Rang).

Sie können eine Korrelation für diese Daten berechnen. Für eine umgekehrte Sortierung erhalten Sie -1 und so weiter.

Kaz
quelle
1
Es tut mir leid, aber dies lässt zu viel ungeklärt, wie Sie die ganzen Zahlen zuweisen.
Marcin
2
Sie benötigen die sortierte Liste, um die Ganzzahlen zuzuweisen. dann ist es nur eine Aufzählung der Elemente.
Kaz
1
Genau das, was ich vorschlagen wollte. Bestimmen Sie die Korrelation zwischen der Position des Objekts in der ursprünglichen Liste und seiner Position in der sortierten Liste. Die schlechte Nachricht ist, dass Korrelationsroutinen wahrscheinlich in O (n ^ 2) laufen; Die gute Nachricht ist, dass sie für Ihre Umgebung wahrscheinlich von der Stange sind.
Peter Webb
2
Ja, nur Spearmans Rho en.wikipedia.org/wiki/…
Lucas
Ich bin neugierig ... entspricht dieser Ansatz der Skalierung der Anzahl der Inversionen?
Clayton Stanley
4

Es gab gute Antworten, und ich möchte der Vollständigkeit halber einen mathematischen Aspekt hinzufügen:

  • Sie können messen, wie sortiert eine Liste ist, indem Sie messen, wie stark sie mit einer sortierten Liste korreliert. Zu diesem Zweck können Sie die Rangkorrelation verwenden (die bekannteste ist die von Spearman ), die genau der üblichen Korrelation entspricht, jedoch den Rang der Elemente in einer Liste anstelle der analogen Werte der Elemente verwendet.

  • Viele Erweiterungen existieren, wie ein Korrelationskoeffizient (+1 für genaue Art, -1 für die exakte Umkehrung)

  • Auf diese Weise können Sie statistische Eigenschaften für diese Kennzahl festlegen, z. B. den Satz der zentralen Permutationsgrenze, mit dem Sie die Verteilung dieser Kennzahl für Zufallslisten ermitteln können.

meduz
quelle
3

Abgesehen von der Inversionszahl ist für numerische Listen ein mittlerer quadratischer Abstand vom sortierten Zustand vorstellbar:

#! 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
Boris Stitnicky
quelle
Ich denke, das ist das Quadrat der Standardkorrelationsfunktion, siehe en.wikipedia.org/wiki/Correlation_ratio . Und gilt gleichermaßen für nicht numerische Listen; Die beiden verglichenen Werte sind die Position des Objekts in den beiden Listen.
Peter Webb
Ich bin ein Einfaltspinsel. Ich weiß nicht einmal, was das Korrelationsverhältnis ist. Wenn ich diesen Wikipedia-Artikel ganz oben lese, werde ich gebeten zu erfahren, was "statistische Streuung" ist, dann "Standardabweichung", dann "Variation", dann "Korrelationskoeffizient zwischen Klassen". Ich habe das alles mehrmals gelernt und mehrmals vergessen. In meiner pragmatischen Antwort messe ich einfach den Abstand zwischen den beiden Vektoren mit dem Satz von Pythagoras, an den ich mich aus der Grundschule erinnere, das ist alles.
Boris Stitnicky
1

Ich bin mir der "besten" Methode nicht sicher, aber eine einfache wäre, jedes Element mit dem nachfolgenden zu vergleichen, einen Zähler zu erhöhen, wenn element2> Element 1 (oder was auch immer Sie testen möchten) und dann durch die Gesamtzahl zu dividieren von Elementen. Es sollte Ihnen einen Prozentsatz geben.

user2369405
quelle
1

Ich würde Vergleiche zählen und auf die Gesamtzahl der Vergleiche aufteilen. Hier ist ein einfaches Python- Beispiel.

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
ibrahim
quelle
0

Wie wäre es mit so etwas?

#!/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()
Dstromberg
quelle
2
Dies zählt nur benachbarte Inversionen. Wenn Sie sich die anderen Antworten ansehen, werden Sie feststellen, dass dies nicht ausreicht.
Konrad Rudolph
1
@KonradRudolph: Ich denke, diese Antwort erfüllt die gestellte Frage. Die Tatsache, dass andere Antworten umfassender sind, bedeutet nicht, dass diese unzureichend ist. Dies hängt von den Anforderungen des OP ab.
LarsH
0

Wenn Sie Ihre Liste nehmen, die Ränge der Werte in dieser Liste berechnen und die Liste der Ränge Yund eine andere Liste aufrufen X, die die Ganzzahlen von 1bis enthält length(Y), können Sie durch Berechnung des Korrelationskoeffizienten genau das gesuchte Maß für die Sortierung erhalten , r, zwischen den beiden Listen.

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}} 

Für eine vollständig sortierte Liste, r = 1.0für eine umgekehrt sortierte Liste r=-1.0und die rUnterschiede zwischen diesen Grenzwerten für unterschiedliche Sortiergrade.

Ein mögliches Problem bei diesem Ansatz besteht je nach Anwendung darin, dass die Berechnung des Ranges jedes Elements in der Liste dem Sortieren entspricht, sodass es sich um eine O (n log n) -Operation handelt.

Simon
quelle
Aber das wird die Kurvenform nicht ignorieren. Wenn sein Array sortiert ist, aber beispielsweise exponentiell ansteigende Werte enthält, ist die Korrelation dort klein, wo er 1,0 haben möchte.
Lee Daniel Crocker
@ LeeDanielCrocker: Ja, das ist ein guter Punkt. Ich habe meine Antwort geändert, um dies zu beheben, indem ich die Werte in die Rangfolge aufgenommen habe.
Simon